There are too many ways for an Exchange Server to be set up for anyone, maybe even your IT department, to be able to tell you why that's not working. It's not like IMAP or POP3, where there's one simple protocol that all servers follow, it's pick one from column A, pick one from column B, etc., etc., until you have the server doing what you want it to do - and that way may not be a way that a particular email client can handle. Outlook, running on Windows, can handle it, and that's all Microsoft is concerned with.
Your IT department is probably correct, but try other "Outlook" apps first (there are a few of them). One of them may work with their current arrangement. (If not, a newer phone probably won't either. Ask your co-workers with Android phones which app they're using.)
As far as your gmail account, set it to retrieve email every zero (or not retrieve, depending on the client you're running). That's Push - the server sends the client the email as it's received. (I sometimes get my desktop email client and my phone saying "you've got mail" (yes, I use that old AOL notification) as a chorus when email comes in, that's how closely they're "synced".
Your other email accounts? No idea. It depends on the server. We've had complaints about Yahoo recently, so they may have changed something. But each email server is different, so someone who has an account on the server you're having a problem with, and who has solved it, will have to chime in here to tell you how to fix it - if there's a fix for the problem. Which means
join the Android Central community so you cn list the servers you're having problems with here, and keep an eye on this thread. (Subscribe to it so you get an email if someone posts to it.)