You can find many examples of backup rotation schemes, like here:
http://www.backupassist.com/education/bsg2.html
We keep (at work) backups for the last 30 days, but that wouldn't solve this problem. It could well be that we are infected for two months without noticing it. In that case: remove by hand or reinstall.
When you use VMs like Amazon EC2, you can use snapshots. For your server or desktop OS, you can make a snapshot or image (disk image on tape or harddisk) of the installation right after initial setup, and right after all configuration is done, but without data. Later you can go back to that image. I use this method for creating vms for local development and testing machines.
You need to test backups on a regular basis. Do they still work? Do they still backup what is needed? Has the situation changed with new servers or data drives so you need to add or remove them from the backup scheme? And have you ever tested if you can restore a backup successfully? That takes time and effort, and you may postpone that, but you need it you better have a good procedure.
Another tip is to use two different backup methods, like one with tape, another in the cloud or using another backup program. For my laptop I use Time Machine and Crashplan.
None of these tips can make it so that nothing ever will be lost.
Sometimes you (or a process) delete(s) a folder without noticing it, and years later you need something in it, and it is simply gone. Once I deleted a mail account in my mail app, not realizing that this deleted sent mails. It tooks several years before I found out, and it was lost. I've had several times that I deleted something on my laptop that I needed later, and sometimes the backups saved me, but not always.
On my desktop I use Crashplan, which can backup everything and can save different versions of documents. But do realize that such a service can go bankrupt and then your backups are lost. You can use this program for local backups, but it seems to be that local restores won't work when CP is offline. So when they go bankrupt the local backups are gone too! Still it's a great service I think.