It seems like maybe you have a "lost write" - toward the end of the article it shows your error and gives a small explanation of what happened:

http://support.microsoft.com/kb/826433

Having said that, I can't find any advice on how to deal with an existing "lost write" that you haven't already tried (everyone says just to SP4 the machine, which you've done) However, (and this is just me thinking out loud) if it is a problem with data pointing to unallocated space, you might try dbcc checkalloc and see if this reveals any errors which were not turned up by the checktable and checkdb.