I've had a similar issue. My mail worked great on my phone for several months, and then when I changed my password, it stopped being able to send. It is always able to download email, just not send it. I've noticed that it does work to send the email when I'm connected to wireless rather than using 3G/4G cell service.
I'm wondering if when yours randomly works it is because you are connected to wireless.
If anyone finds a fix for this I would be interested, but at the time, to me, it seems to be a problem with Sprint. (and i've been too lazy to call them)