Are you still on SQL Server 2000??? This was a know issue in SQL Server 2000 - What causes this issue is if a row gets deleted by spid 1 while spid 2 is doing a scan with (either at READ UNCOMMITTED or WITH (NOLOCK)), then spid 2 face issue when it tries to read it. The row has to be deleted after spid 2 reads the index, but before it attempts to read the data row.

Microsoft released a fix for this issue: http://support.microsoft.com/kb/815008

Thanks..

Sanjiv Vinaik