Deadlocks And Parallel Query Processing

SQL Server 2000 SP3A

Last week one of our processes starting issuing or suffering deadlock
detected errors every 15 minutes or so.

I have read several articles at MS on the subject. I set a couple of
startup parameters related to producing deadlock detection information
and ran SQL Profiler. I found the SQL statements being issued by the
deadlocked statements. In every deadlock the same UPDATE statement
appears however the data values being searched on are different. The
best I can tell from trying to query the actual data each update hits
only one or very few rows. No indexed column is updated so the indexes
should not be the source of conflict.
Looking at the query I noticed that the query does not have an
available index and Query Analyzer shows that the full table scan is
being done in parallel.

My question: Does SQL Server change or modify its locking rules when
queries are converted to be ran using parallel processing? If so, do
you have a reference?

Here is the deadlock entries posted to the error log:
SPID=167
ResType:LockOwner Stype:'OR' Mode: IX SPID:63 ECID:0 Ec:(0x65971510)
Value:0x3c577e60 Cost:(0/0)
Input Buf: Language Event: UPDATE Station_Upload set
Station_Accept_Status = 'ACC',HeadStatus =
'ACC',LastProcessedSta='110',HeadPartType='1' WHERE Part_Serial_No =
'SCH1119323' AND Station = 'H110'

SPID=63
ResType:LockOwner Stype:'OR' Mode: IX SPID:167 ECID:0 Ec:(0x65801510)
Value:0x3c27d060 Cost:(0/0)
Input Buf: Language Event: UPDATE Station_Upload set
Station_Accept_Status = 'ACC',HeadStatus =
'ACC',LastProcessedSta='70',HeadPartType='1' WHERE Part_Serial_No =
'SCH1119060' AND Station = 'H070'

I have suggested adding an index to support the query.

Any ideas?
Thanks -- Mark D Powell --