To add more information to this, this does not seem to be related to an increase of the log file. Tonight, the log file was shrink and the delete command generated the same behavior. While it was executing, no one was able to insert into that table because of a deadlock.

I really do not know the trigger of such situation that starting to happen about 10 days ago. We never had the situation before. I was able to delete a few thousand records every 15 minutes and this was not impacting users on the Web site which were doing hits, thus creating new records in the same table. The only think I could see is that the number of records that have to be deleted every 15 minutes is bigger than before. This may create a situation that SQL Server is now forcing a lock on the table during that timeframe.

Having said that, unless I can find the cause of all this, I need to find another technique for deleting those records. The only one I could see presently would be to delete them one by one in a For/Next loop. I still need to do some benchmark tests to see if the performance would be adequate and if this would avoid the deadlock situation. There is also a possibility of recycling existing records in realtime, thus replacing instead of inserting, but this is something I would rather not consider as this would create a primary key situation and would break the chain of records.