The only other thing I would suggest is trying the first half of #5 from my previous list:
5) Try logging in as a different user. I'm not sure if your corporate environment is using roaming profiles, but if it is, then this could eliminate a few things. Open up Outlook under the different user account and try printing an e-mail. If the problem doesn't occur here, then the user's roaming profile might be corrupt. To confirm this, log onto another PC with the user's account that is having the problem, and try to print. If the problem exists, then yes, indeed, their profile is corrupt. Start rebuilding that profile!
You tried the second half of this (different PC, same user), but not the first (same PC, different user).