Haven't had that problem before, far more of a problem when I try to register with site specific email addresses like d+hn@nblows.com which I've tried to get in the habit of doing.
Are there many providers who support one, but not the other?
It's quite a convenient way to have site specific addresses while still only having a single mailbox to manage.