A good rule of thumb is to try and set it up as Mail.Server.XXX.net
For example, I use Optimum Online, and my mail server is Mail.server.optonline.net. (Generally it's the same as your e-mail's tag... worldnet, sprintnet, etc etc.)
If that doesn't work, go to the company website of your service (or post it here, someone might know offhand) and look around in the Faqs, or customer service.