Yesterday we found and fixed a critical bug in our backup server configuration.
A typo in the exclude file caused PostgreSQL write-ahead logs (WAL) not to be backed up. The PostgreSQL heap, which contains regular table data, has been backed up constantly though. This means that we were able to restore PostgreSQL data, but could not guarantee a consistent restore of transactions started between the last checkpoint and the time the snapshot for the backup was made.
The bug has been fixed yesterday. We have verified that all PostgreSQL servers' write-ahead logs have been backed up tonight so restores from backups performed since 2012-05-16 will not suffer from this problem.