I've read through posting about this problem. Have been in contact with my Provider, Verizon and I'm still having problems with not being able to connect with the server for mail.
I can be on the 3G network or WiFi, both with three bars. Surfing the internet is no problem. I am receiving email on my computer but not on the Fascinate. Sometimes the situation will last for several hours and then 30 messages come through.
My internet provider told me that it's a know issue with the Fascinate and OUTLOOK . . .but not sure if that was BS or what.