Not sure if this is relevant, but I had a very similar problem with AT&T, who, IIRC, was using Yahoo SMTP servers. This had worked okay for years, but then suddenly I was having to send and resend messages multiple times until they would actually go thru. This was a huge pain. At that time, I suspected that AT&T or Yahoo had cut back on their SMTP servers since most people were now doing webmail. That meant that I was now finding their reduced number of SMTP servers busy, and there was no chance that I was going to get AT&T/Yahoo to backtrack on their reduction.
My solution was to find an alternate SMTP server. There are places out there that offer this as a service. I looked around and found authsmtp.com. I have been using it for several years and it has worked flawlessly. I use their minimal subscription which I believe covers up to 1000 outgoing emails a month for a cost of US$32 per year. I believe I can register up to 10 sender email addresses within this plan.They want you to pay by the year, but they allow you to cancel and back out in the first month if you're not satisfied.
They also seem to take spam very seriously, so I don't think I'm supporting a spam farm.
Since my POP server is also not AT&T or Yahoo, this now means that I'm not tied to them in any way, so I'm free to change ISPs without fear of having to change email addresses or anything else. I've used this while traveling around the US, no problems. I assume it would work equally well, anywhere in the world that had good internet access.
I have no connection to authsmtp other than as a satisfied customer.