I'll confirm some of these findings.
Yesterday when I setup exchange, I had set it up at home. Sending myself messages from a home computer to test, push was working perfect (I have wifi at home). Today at work I noticed that push wasn't working. I tried turning off the phone, removing the exchange account from the phone and redoing everything, etc. Nothing worked. I thought it was broke. I connect via wifi to the intranet at work.
So here I read this thread while waiting for class to start, and decided to send myself a message via web version of gmail to my phone. Email came instantly!
So in my eyes, it's true that exchange does not if connect via wifi at work. I'll have to talk to the it department to get this resolved.