Just to complete the topic, Old Hands was right (proved on a similar case): DBCC CHECK DB found references to non-existent columns in some legacy stored procedures. After these...

As a side note, data consistency generally follows business gogic. in some cases it has to be inconsistent (say, order history of deleted customers)

Check out SP4 available from MS since April 2002. http://www.microsoft.com/sql/downloads/sp4.asp

"Because SQL Server Service Packs are cumulative, SP4 includes all fixes from previously released Service Packs, and can be applied to...