[FionaVB]

There's an old song called "Miss Otis Regrets" whose chorus goes "Miss Otis regrets she's unable to lunch today." (It turns out she has just shot her lover.)
Maybe part of the reason that "I regret she has left" sounds funny is the meaning - usually you regret something you have done yourself. You can say "It is regrettable that she has left" but although I can be sorry that she has left, I wouldn't regret it, I think.