Gmail is the way to go! I used to hate webmail and only used pop3, but after all the buzz with gmail when it had the beta invites, I decided to check it out. After using it for a month, i never went back to outlook. I highly doubt they "hacked" your gmail. You either had a keylogger on "your" computer or must had a really simple password.
i use recovery option and access to my gmail again but hackers can use of this option too For example my new gmail account hacked again "irdrupal1@gmail.com" only use recovery option , the hacker would want hack my site and try to find my emails to hack it , for this reason i don't want use gmail again , i think this is better that i create a personal mail service for myself and my users ...
All are worst they can get any info about u , ur privacy , ur searches etc. Setup a new Mailbox and try it