I think I'm going to write a STW Frequently Asked Questions guide…!
As a rule of thumb, when setting up email you need to use your email provider's settings for inbound (pop3) email and your service provider's settings for outbound (smtp). So, eg, setting up Virgin email on an O2 phone, pop3 would be virgin and smtp would be O2.
Additionally, some smtp providers now require you to authenticate and / or use a secure connection. This may require a different port to the default (25) and varies between providers – check their website.
Finally, contrary to the above it is sometimes possible to use your email provider for smtp rather than your service provider, however you will definitely have to authenticate in this case (otherwise the server sees a foreign connection and drops it as an anti-spam measure).