Oooh, what fun getting that sorted.
BCC - less load on your server, batch up into groups of, say, 100 and send
Individual - you can put a hyperlink on saying if you want to unsubscribe click http://www.mysite.com/unsub.php?id=123
where 123 is the id in your email table - don't have an id - get one!
I think the individual is the way to go but you may want to check any limitations with your isp.
Now, invalid emails
When I sign people up I check their email address and bounce it back to them if it's invalid. That doesn't get me past the poor guy with tom@aol.com. That means that all addresses were valid when they were entered. Then the bounces after that I don't worry about, they're insignificant in number.
However your ISP has probably given you a number of mail accounts and you could set up an email address like mailshot@mysite.com and use this as the senders and reply address on your email. Then use php to a) clear the pop3 account, b) delete the emails and c) mark the email as invalid.
This however may not work as when I do it I get a single email back from an isp with a list of names where the email has failed (in the case of the BCC example). Each one has a different format so you might need to do it manually the first time until you get your systems sorted out.
I also send my emails as html email. I use phplib to get the body and then pass it to the html email class. This means that I spend very little time creating and sending the emails, my code is clear and easy to read and the delivered email looks first class. Again, your ISP may not appreciate your sending thousands of these but...
Resources:
http://sarah.users.phpclasses.org/browse.html/package/13.html
http://sarah.users.phpclasses.org/browse.html/package/32.html
click through the mirror bit and you'll be taken straight to the page.