Hitting purge or moving deleted mail to the trash manually may help with part of your problem, but the strikethrough is outlook's way of saying its deleted but not permanently removed from gmail. Same scenario with your spam, it is blocked by outlook but not through gmail and displays with a strikethrough. I'll let you know if I hear of a workaround for this, but as far as I know this is the way IMAP works between outlook and gmail. Make sure you set it up according to "GMAIL's instructions" though.

Here is more info about what outlook actions do in gmail when setup with IMAP:
http://support.google.com/mail/bin/answer.py?hl=en&answer=77657