You should find someone with another device and try to set up your mail on thier device. If it doesn't work, then you've narrowed it down to your outgoing settings.
With the Samsung Galaxy S I notice that certain exchange servers do not work on it - they work on every other device I've tried. So.. I'm just recommending people against the Galaxy S. I was fortunate enough to have access to multiple Galaxy Ss though (as well as other devices). I doubt you have a bunch of PPCs readily available