I've set up a catch-all SMTP server for my domain and now I make up unique addresses on the fly. It simply forwards everything to gmail. Was too lazy to set up sending.

Thanks to this setup, I've already encountered one instance of a company either leaking or selling their customer information.