Oh gosh, SMTP settings are a swine to troubleshoot! It's not uncommon for network-provided services to work only via a connection through them. If the mail service isn't attached to a network (eg BT), then that's not going to be the issue. The message you're getting looks pretty conclusive, but failures sometimes trigger the wrong one. In the first instance, I'd try different security settings, SLS/TLS being the most common. Different mail programs have different ways of laying the settings out, but what needs to happen is that you sign in before attempting to send (sometimes shown as "requires authentication"). It sounds as though this is what's happening, but check all the available settings.
What happens over wifi - both at home and out and about? It's unlikely to be a Vodafone thing, simply because the network will just be transmitting the request to the mail server, but the app may be mis-reporting the issue.
If all else fails, it may be possible to use the Gmail server, but that'll result in your messages being sent as Gmail. In that case, it's easier to shift the whole thing over to that platform and use the Gmail app. You can still use abc123 as the underlying service, though and someone here can talk you through that if it proves to be necessary.
