Yes this is possible. Which ISP are you with and which e-mail client are you using? (Outlook Express, Outlook) It depends how many people are in your address book as to whether your ISP (Or indeed your Anti-Virus) will let you send all the messages at the same time. Anti-virus will kick in if a certain number of messages are sent within a certain time frame - it is looking to detect virus activity, so you`d better tell us which one you are using.
Basically I think you check out the above first and then set up your new e-mail address and do a couple of test messages. Compose your notification e-mail using your new address - I would include instructions for the recipients to add your new address to their own address book. (e.g. In OE open the message and then select Tools>add sender to address book)and delete your old one. Then select the To: and send the message to yourself. Then select the address book icon next to the CC: and your address book should open. You will see an additional pane for BCC. Highlight the first name in your address book and then scroll down to the last. Hold down the SHIFT key and click on the last address - the entire address book should be highlighted.
Now click the BCC tab. (Blind Copy means that none of the recipients e-mail addresses will appear at the top of each e-mail thus protecting your address book privacy and saving potentially a long list of addresses!)
I would stress you should check out the details first and post back so we can check it out. Also note that spam is prevolent and there`s no guarantee that this will stop it. Have you tried Mailwasher for example? This will preview your mail and allow you to blacklist senders before the mail actually gets downloaded from your PC.