Also, I've tried escaping the # as:
# (C-style)
#35; (HTML-style, using delimited ASCII value in decimal notation)
#035 (fixed-length ASCII value)
## (typical "repeat the special character" approach)
And I've done all of this in a telnet session, so don't let my mention of Outlook Express suggest that the fix should be done there. No stateful inspection firewall in the middle, neither. Just plain bug in Exchange.
As best I can tell from RFC2060, either quotes or the escape character should do the trick, subject to any implementation-specific password requirements. And there isn't a more Windows-specific messaging product than Exchange. If only we were Premier so I could demand a QFE...