Thanks, we were rebuilding the DBs from scratch, but the errors keep reoccurring.
After a bit more research I turned up this article: http://support.microsoft.com/kb/940126. As we are on SP2, looks like applying Service Pack 3 should resolve the problem.