Your particular problem is most probably their policy of deleting all emails after a certain period of inactivity (90 days if I remember correctly), happened to me too once..
Microsoft's online services division loses $100M-$200M each quarter.
Google retains the data indefinitely because it's in their best interests not because of their dedication to the user. Why else would they retain even what the user deletes?
>> we have a policy of deleting emails after 270 days
http://www.reddit.com/r/IAmA/comments/ej32l/we_are_the_hotma... (do a search for "270" on the page to find the quote)
Although I have no idea when they changed it to 270 - it can't have been that long ago.