What would you do if you realized your email hosting provider could see your passwords?

Yes, it is common for ISPs and email service providers to store your password in plain text, or a format which is easily recoverable to plain text.

The reason for this has to do with the authentication protocols used with PPP (dialup and DSL), RADIUS (dialup, 802.1x, etc.) and POP (email), among others.

The tradeoff here is that if the passwords are one-way hashed in the ISP's database, then the only authentication protocols that can be used are those that transmit the password over the wire in plain text. But if the ISP stores the actual password, then more secure authentication protocols can be used.

For instance PPP or RADIUS authentication might use CHAP, which secures the authentication data in transit, but requires a plain text password to be stored by the ISP. Similarly with the APOP extension to POP3.

Also, all of the various services which an ISP offers all use different protocols, and the only clean way to have them all authenticate to the same database is to keep the password in plain text.

This doesn't address the issues of who among the ISP's staff has access to the database, and how well it is secured, though. You still should ask hard questions about those.

As you've probably learned by now, though, it's almost unheard of for an ISP's database to be compromised, while it's all too common for individual users to be compromised. You have risk either way.

See also Am I wrong to believe that passwords should never be recoverable (one way hash)? on our sister site IT Security

This is, unfortunately, fairly common with budget hosts and not unheard-of even with bigger hosts. Things like cpanel frequently need your plain text password to be able to log in to various services as you, etc.

The only thing you can do is to ask upfront if the passwords are hashed.

They're likely either storing passwords in plain text or using some kind of reversible encryption.

As you've surmised, this is very bad.

Either due to employee maliciousness or negligence, or a compromise of their systems by an outside party, the plain text passwords being misused creates a serious risk - not only to their systems, but to other systems people might have used the same password on.

Responsible storage of passwords means the use of one-way hashing functions instead of reversible encryption, with a salt (random data) added to the user's input to prevent the use of rainbow tables.

If I were in your shoes, I'd ask the provider some hard questions about how, exactly, they store passwords, and how, exactly, their support rep was able to retrieve the password. This might not mean they store the passwords in plain text, but maybe they're logging them somewhere when changed - also a huge risk.

All the other answers are great and have very good historical points.

However, we live in the age where storing passwords in plain text causes huge financial problems and may utterly destroy businesses. Sending passwords in plain text via insecure email also sounds ridiculous in the age of NSA sucking all passing-through data in.

You do not have to accept the fact that some old protocols require passwords in plain text. If we all stop accepting such services, probably the service providers would do something about it and finally deprecate ancient technology.

Some people can remember that once when you want to board a plane to flight to another country you would literally just walk into the plane from the street parking. No security what so ever. Nowadays, people realised that appropriate security measures are required and all airports have got them in place.

I would switch to another email provider. Search on "secure email provider" yields many results.

There were some good points in the comments. Probably search for "secure email provider" would make much sense as all email providers would boast they are secure. However, I cannot recommend a particular company and it's probably not a good idea to do either. If you identify a particular company asking hard question about security first will be a good thing to do.

My recommendation is to leave, and ask the next guys what their policies are first!
If you're feeling nice, you can tell the old providers why you are leaving.

Also to address another answer's statement, the days of rainbow tables have passed. They have been superseded by high-powered GPUs and take too much storage space (binary hashes obviously don't compress well; and you wouldn't store them in ASCII anyway). It's faster to (re-)compute the hash on a GPU than to read it off the disk.

Depending on hash algorithm used and the GPU, a modern password cracking computer can be expected to churn through about 100 million to a billion hashes per second. According to this, (which is a bit dated on what it thinks a computer/supercomputer can do), that means any 6-char password can be cracked in seconds. Tables for 7 & 8 char hashes in all the various algorithms (MD5, SHA-1, SHA-256, SHA-512, Blowfish, etc.) would consume inordinate amounts of disk space (realise that you need to store them on an SSD, not a magnetic platter, for access speed) and you can see why dictionary-based attacks using the GPU are going to yield passwords more quickly.

A nice article for those coming into the scene is How I became a password cracker at Ars Technica.