I used to have this problem with Gmail because it was easy to receive mail at a new address, but always a 10-minute process to start sending mail from a new address.

I just switched to Fastmail and was pleasantly surprised with their solution. You can set up wildcard response aliases so that if you receive an email to [email protected], when you hit reply, it automatically sends from the [email protected].