Huh, very interesting. This might be the source of another outstanding issue that I have yet to pin down. Thanks for the very simple steps to reproduce, I'll look into this issue and report my findings here.
Out of curiosity, is this functionality you need that you wrote or is it just part of a plugin that you use? I ask because if I can't find a solution to the core add_rewrite_rule() function my next best strategy would be to provide an alternate method that you or others can call. This obviously doesn't help you out if it's third party code, but even then I could work with the third party if it's a big enough problem and if they're willing.