(I tried to duplicate this with Fido Canada, and only received the expected "there may have been a problem" error. I'm not yet sure which provider caused the bounces.)
Anyhow, while the format of the local part of the email address on email-based services is hard to predict, I think it's a pretty safe bet that spaces will never appear in there. I'd like to try to rejuvenate bug 1316 to fix only that, in order to not awaken bug 241 whose scope is IMO too large to ever get resolved.
I figured I should mention it here before I touch it there, though. Any concerns or objections to stripping only spaces from only email-based providers?