Ynyshir, because you can get the Internet fine, you don't need to change anything in the Internet Options panel.
Are you using Vista's "Windows Mail" program? If you are then try this:
In Windows Mail, click the "Tools" menu and choose "Accounts". Locate the affected mail account then double-click on it. In the "Properties" window that should open, click the "Connection" tab and remove the tick from "Always connect to this account using". Click OK when done and try your emails again.