That is a very interesting result. I found this article on Outlook and winmail.dat that points out that you may need to clear Outlook's autocomplete-cache as well as changing the mail type to plain text or HTML to get it to stop sending winmail.dat files to certain addresses:
http://www.slipstick.com/problems/outlook-is-sending-winmail-dat-attachments
Show it to your IT guy and see if that's what may be happening. E.g. the iPhone Gmail acct is one you've been sending stuff to for a while and it used to be set to send as RTF, was changed to HTML/plain text at some point but autocomplete-cache is still saying RTF and overriding the new setting, whereas the Android Gmail account is new and has always been set to send in non-RTF format and so does not have the problem.
(There is an additional possibility -- we know web-based Gmail automatically extracts content from winmail.dat attachments in incoming mails. Perhaps the Android Gmail app does this too? So it may be that the emails to the Android phone acct are actually being sent with winmail.dat attachments from your Outlook/Exchange acct but they are being automatically removed by the Android Gmail app so you never see them. If you're really keen then try using another email client for reading the mails at that Gmail account - preferably a Mac or Windows PC running a non-MS email client like Thunderbird or whatever. Does that get winmail.dat attachments or not?)
As I this is all fascinating stuff, but the point surely is to stop having to worry about winmail.dat files? (i.e. to drain the swamp).
Even if you manage to stop the emails you send from your Outlook/Exchange acct to your Gmail/iPhone from using winmail.dat attachments there's no way to prevent other users from other organisations sending you such emails at any time in the future. So why not just install one of the winmail.dat handler apps from the app store and rest easy? Why muck about endlessly trying to figure out whether it's some obscure setting in Outlook and/or Exchange or some weird interaction between Gmail and Exchange that is causing them in this particular case?
With a winmail.dat app installed on your iPhone or iPad you don't care who sends winmail.dat attachments to you or why, you never have to worry about winmail.dat again.