I have a fairly public email address (or certainly used to be), and get about 150 mails a day.
Here's a good tip to stop them:
Goto gmail.com, set up a free gmail address.
Gmail can collect mail from other email addresses (such as your current one), and it'll then apply its own spam filters to your mail. So you can then use Gmail, still acting as your current email address.
Make sense?
That way, you won't have to inform anyone of your new address, and you'll still get email. Just the filters will move most spam into the spam folder, which you can check once every few weeks.