The best situation for me has been one of my personal projects. It's a gaming site that I use everyday. The database dump is less that 100MB gzipped, so I load it in my development environment every week or so. That way as I develop I'm verifying (to some extent) the quality of the backup.
As a baseline, you should at least restore from your backups occasionally.
It helps that I'm familiar with the data -- so after restoring the backup I expect to see games, messages, forum posts, etc that I've just seen in production.
I do some more thorough automated tests on the backups less frequently. App specific things, like replay games and verify results, etc. This process is more about assuring backward compatibility with the code though.
I think verification should ultimately be somewhat app specific. That said, I'm sure you can find tools to help with verification.
