recommendations:

1) see here:

http://blogs.msdn.com/bartd/archive/2006/09/09/Deadlock-Troubleshooting_2C00_-Part-1.aspx

Note there are 2 additional parts to this blog series.

2) as someone else said, you will likely need to batch up the DELETE.

3) you might also need a NC index on the date you are using for one of the deletes.

4) get a professional on board to help you. That sounds like a very complicated process and you might need some difficult refactoring to get everything to play nicely.