For websites, in theory, you could have saved that email you get when you sign up for a new service (message boards, mailing lists, youtube/myspace/whathaveyou), the one that says "keep this email for your records", and probably contained some default password that you had to change?
A professional company (and free/oss software that generates these types of emails) probably includes a way to change that info with a link in that email (or a form on their site).
My hotmail account pretty much only contains those types of emails at this point in time, as that is why I created it. Yes, it would time consuming to switch, but hey, it's your choice in the end.
Unix soit qui mal y pense [Unix to him who evil thinks?]