The id could be anything, and the SHA1 HMAC takes 32 characters in base32 (which is an email-address-safe encoding). Then just configure your spamfilter to reject any address where the HMAC doesn’t check out.
Of course, the drawback is that you’ll need a computer to generate a new address… At which point you may as well store an explicit whitelist of valid addresses.