Same problem here. Forwarding domains into Gmail and using Send as worked fine until it didn't.

I ended up building my own solution (Mailyond) to have all my product domains under one place.

What solution are you looking at?

Same, although I have multiple domains

Are you looking at a real mailbox provider, or trying to keep Gmail somehow?