(This is meant to be a comment, but I don't have enough reputation to add a comment yet...)
You just fried my brain. In my Cygwin, the same thing happens. I was shocked. It appears to be a bug in how the wildcards are handled, whether they are using regular expression syntax or glob-style (glob--style is where * means 'any number of any type of character', regular expression * means '0 or more of the previous characters'.
So I tried it in my QNX shell. It works IFF I don't try to use a plus before bug, as in "s/^ +bug-/__/". I can substitute a * in place of the + and it works. I think some implementations of sed are having a hard time picking regex or glob syntax and the result is an unpredictable mess.
I didn't try Perl (haven't installed it yet on this new machine), but I would be doubly shocked if Perl handled it as poorly.
To answer your question, to the best of my knowledge and ~100,000 of my closest friends on Google, your understanding of how the ^ operator should work is accurate.