I agree with the suggestions to batch your deletes into managable chunks if you aren't able to use TRUNCATE, and I like the drop/create suggestion for it's originality, but I'm curious about the following comment in your question:
It's basically equivalent to a TRUNCATE TABLE statement - except I'm not allowed to use TRUNCATE
I'm guessing the reason for this restriction has to do with the security that needs to be granted to directly truncate a table and the fact that it would allow you to truncate tables other than the one you are concerned with.
Assuming that is the case, I'm wondering if having a stored procedure created that uses TRUNCATE TABLE and uses "EXECUTE AS" would be considered a viable alternative to giving security rights necessary to truncate the table directly.
Hopefully, this would give you the speed you need while also addressing the security concerns that your company may have with adding your account to the db_ddladmin role.
Another advantage of using a stored procedure this way is that the stored procedure itself could be locked down so that only specific account(s) are allowed to use it.
If for some reason this is not an acceptable solution and your need to have the data in this table removed is something that needs to be done once a day/hour/etc, I would request that a SQL Agent job was created to truncate the table at a scheduled time each day.
Hope this helps!