Microsoft screwed the IMAP feature in Outlook 2007 (they fixed it with 2010 tho).
In 2007, go to Tools->Account Settings, select the account and Change; go to More Settings, and check "Purge items when switching folders while online". Then Ok out.
The strikethrus will still happen (IMAP messages are not automatically moved to Deleted Items), but when you switch folders and come back, anything with a strikethru will be purged forever. If you still want to use the Deleted Items folder as a middleground "I want to keep my Inbox clean, but maybe I don't want this gone forever", you'll just have to click-n-drag to that folder, instead of using the delete button.
I hope that helps.