Ok, so I suspect all you are doing is option a below? What they want is that you also do option b as well. There is really no way around it other than to send all your existing users an email asking them to click a link to confirm they do wish to receive it and of course do that from now on. The alternatives are place the newsletter mailing list on a different host or even use a specific service that handles newsletter opt in for you (mailchimp).
a) User ticks a box saying they want your newsletter and enters their email address.
b) They need to confirm they do want the newsletter by clicking a link in an email you send them.
Dealing with the inevitable abuse reports that even come from double opt-in is painful for web hosts. We spend a lot of time working hard to keep our IPs clean and one or two errant emails like this can dirty them and cause mail delivery problems. With this in mind, I’d recommend something like Mailchimp or ConstantContact.
To process double opt in you need to add an extra field to the database record you create when they first sign up and generate a random code to place in that field.
Next you send them a confirmation email to the address that they signed up with that asks them to confirm that it was them that signed up by clicking on a link at the bottom of the email. That link should call a script passing it the email address and the random code. If the random code matches that in the record you saved in the first place then this script should delete the value from that field to indicate that the double optin is complete.
You should then only send out the newsletter where that code field has been blanked out by the person clicking the link in the first email you sent them when they signed up.