I've got it to work, somehow. I left the settings as they are and did a soft reset a couple of time and it worked. I actually gave up but it worked in the end without me realizing.
Another thing I've learned by messing with the settings, I can actually sign into Pocket MSN by taking out the proxy settings! This makes me very happy. I've also tried the same thing on my previous phone, the T-mobile MDA (Wizard) and the ended up with the same result!