Miguel,
I have just read this:
http://www.buzzwebtips.com/recycled-email-account/
So regarding Gmail it seems you're right but as for Yahoo and Hotmail see for yourself...
One more thing: I've already said I don't trust free services!
No one can guarantee that sometime in the future they won't change their policy and allow recycling deleted usernames.
Get yourself a domain and your problem is solved!