Whether on Google Apps or using Exim, all my domains have a catch all address so emails to unmatched local names (addresses) are sent to a single inbox. I then use [email protected] for registration at each service.

It's not much more difficult to circumvent than gmail's +randomname but a little fuzzier. There's no way to know from the outside how many people are using each domain.