opc.three, first, thanks for pointing out the USE statement. I simply missed that. Second, I just re-checked and the procedure is correct.

I'll admit, in all my testing, I failed to look at the execution plan of the procedure. I was looking at the actual deadlock graphs and information coming from the deadlocks and trace information. I looked at the plan both ways and I do see the difference.

Things make even less since this morning. We removed the Foreign Key constraint and we are still getting deadlocks because the UDPATE on TableA is still putting an Exclusive Key Lock on the Primary Key of TableB.

I am going to make sure everything has recompiled and all statistics have been updated as well as digging deeper into the database and see if there are any other hooks. I just knew it was the FK somehow BUT it seems that I was wrong.