I'm sure you've already heard plenty about Skype's recent account hijacking vulnerability whereby attackers could hijack a Skype account by adding the target user's email address to an account and then performing a password reset sent to their *own* account. All that was required to hijack the account was the email address of the target user.
A simple trick I use that would have foiled the above issue (or at least made it more difficult to execute) is to insert a few random characters into my email address in a way that doesn't prevent it from functioning. There are two quick ways to do this that I know of; either by using Gmail or by using a catch-all/wildcard address on your own domain.
Gmail ignores anything in your email address following a "+" sign and before the "@" sign. The idea is that you can put key words in that spot to use for later filtering and labeling inside Gmail. For instance "foo+BAR@gmail.com" is the same as "email@example.com" or "foo+FIGHTERS@gmail.com". Instead of a label, you can include a few random letters in your address when creating new accounts which Gmail will ignore, but which will make it potentially more difficult to determine what address you used on any given site. (i.e. "foo+4Gh8unS@gmail.com")
Using your own domain
This one is probably obvious given the above, but if you create a wildcard address you can then use any random username at your domain. That can be a drag if spammers start spoofing your domain, so as a work around you can include a keyphrase in the email name and then use filters to pass those messages through to your inbox while rejecting the others.
Not going crazy because of this
This really only works if you trust your browser to store your username for logins or if you use a password manager like LastPass. Otherwise, you'll have to remember your random username for every site, which goes out the window in about 5 minutes.