Automattic (Makers of WP) have a paid service called VaultPress. We have never used it, but it gets high marks.
Personally, we have use a two prong backup plan. (We have done manual backups ourselves in the past as well)
1 - We use a plugin for DB backups (Same plugin mentioned above actually!) so we ALWAYS have the latest database backup stored on a remote server.
2 - When we have a catastrophic failure, we get our host to restore to the previous day for us. Its a single email, quick, easy and done within 1 hour. (Less time than doing it ourselves)
We have several WP installs on various VPS setups, and on the few occasions we have needed a restore from backup, it was a $25 fee from our host to restore a site from the previous days' backup.
In the end, we found it easier and more cost effective to let the hosting company handle our WordPress site backup plans. For the $25 per incident fee, its much cheaper than managing it ourselves.
I'm not saying its the best solution for everyone, but it works best for us, at this time.