Re: Well worth doing
You don't need catch-all, just remember to create the address in their management panels before you use it. But even 1&1 and the cheapy 99p domain places don't care how many you have as the number of email aliases doesn't affect a domain host at all, generally.
The solution for the techy people - make a secret format. For example, have the username (before the @ prefix) contain a number with, say, the number of vowels in the username itself (e.g. fred1, barney2, etc.) or some such way of identifying valid emails you've given out (e.g. just prefix them all like valid_username or somesuch). Then just reject ANYTHING that comes in on a username that's not compliant with whatever policy you've chosen.
Still unlimited aliases. Still all at your domain. Easy to remember/create. Stops all the spam username-guessing. Can be implemented with a manual filter on the end account.
Personally, with the above, going to a server under my control, implementing postfix, postgrey (greylisting), Spamhaus and then forwarding to a third-party webmail service the spam I get is zero except to those addresses that I know are spam (e.g. forum signup accounts). Hell, the underlying account gets spammed more than my domain, and that's not EVER been advertised anywhere (I have no need to). Solution: Block all mail directly addressed to the underlying account that wasn't originating from my server. Or just IMAP into your server mailbox direct (but I don't like the thought of running something like SquirrelMail on my own server for web access, to be honest).
Biting the hand that feeds IT
