Large DELETEs muck up table statistics and cached joinplans, which is why a lot of enterprise databases have an IsDeleted column on their large tables. Setting things up this way has the added benefit of being able to easily "delete" things without too much anxiety.

Ideally, all SELECT queries are forced through a view layer (which already has an IsDeleted = 0 restriction), and you can just schedule a nightly job which deletes or archives all the rows with IsDeleted = 1, then refresh the table statistics automatically.