I emailed Midcontinent, sending a link to this thread and this is their reply:
"Thank you for contacting Midcontinent Communications.
As stated previously, we don't have an authenticated SMTP server available for an outside Midcontinent connection. You can connect to email through any connection Midcontinent services.
Connections from outside the Midcontinent connection will not allow SMTP traffic at this time. Since you are utilizing a connection from another network when checking email with a smartphone (other than a Blackberry, they have their own server they use and have not dropped the SMTP servers like most cell providers have) then you would want to find a solution through the network provider you are making that connection with.
We do have WebMail available for customers who would like to send messages while away from home at mail.midco.net.
We value you as a customer and appreciate your business. If you need further assistance, please reply to this email. You can also visit one of our Customer Service Centers or call 1-800-888-1300.
I guess it doesn't look good for us Midcontinent users. :-(