Not sure what could be happening here, I've pinged a corruption expert to get some advice.

Just one question first, pick a table that has this problem and run the following queries please and post the results.

DECLARE @tblName sysname

SET @tblName = 'LargeTable'

SELECT name, type_desc FROM sys.indexes WHERE object_id = OBJECT_ID(@tblName)

SELECT name from sys.key_constraints where parent_object_id = OBJECT_ID(@tblName)

Does ALTER INDEX ... REBUILD give the same error?