I use the paid fastmail service and it doesn't get spam to the fmail address (some spam to my aliases)
I picked fmail.co.uk as the domain, and a nice long name, so it might depend on the domain.
Since there is no difference in domain between the paid addresses and the free ones I bet nobody dares block the fmail domains, so it would be a decent option.
I think the free account dissolves if you don't use it for 3 months, but i can't see that being a problem.