Whatever solution your choose, you should have a regular backup process.
It's not that gmail could lose your emails. It's that email could lose your emails.
Reliability is the most important concern.
You really think there is someone out there with a better reliability record than Google on this front?
They had 99.99% uptime last year: http://googleenterprise.blogspot.com/2011/01/destination-dia...
I'm on the paid Google apps and my account is intact (I'm not sure if any apps accounts were among those disrupted) but as far as I can tell if you're looking for a reliable web based email service Gmail is your best bet, you could periodically download emails if you want to feel safer.
I doubt a paid email service will be anymore reliable than Gmail. Your best bet is probably to look into a good backup strategy. For example, you could use Outlook or Mail to retrieve all of your Gmail locally while still keeping the original email on Gmail.