The biggest issue I can see with this is the overhead of checking all links for media site matches... but maybe something can be done. I'll take a look.
Yeah, that was my first inital thought as well, as you'd have to run through all of the links to see if any matched.
That said, you could always put a checkbox at the bottom of the edit box (say, left aligned on the row of the buttons) saying 'Don't autoembed media' - or something less clunky, you get the idea!
Or have a button on the toolbar that you press and it scans through the post and converts the links to embedded media. That would make both camps happy - if you wanted it to auto embeding then just click the button before you post.
or #2 - it scans the post when you make it, if it detects any embedable links it asks you if you want to convert the links to embed the media (with a 'remember this' checkbox so if you always want to you can tell it, so you don't get continually prompted).