Ok to summarize,
deadlock was caused by different transaction taking a range lock and row lock at the same time on the incrementing table.
ASP.NET SQLDependency uses ROWLOCK hint for the triggers to remove the deadlock scenario. It however this introduces blocking behavior so that if 2 transactions are modifying the same incrementing table, the transactions are essentially serialized.
A recommendation from MS Support is to change ROWLOCK Hint to READPAST. This reduces the blocking behavior if different rows within the incrementing table are being modified simutaneously.
Since notification does not require absolute ACID properties of the RDBMS, An advanced strategy could be to use a non blocking global variable like context_info as a set of binary flags to store the fact that a row has changed (this would remove the blocking on the same table), however requires logic change on the calling application to handle and reset the variables.