There are other alternatives for outside embeds, like Media Fire or even MySpace. Your best bet is to host the videos on your own site so you retain control over the files.
I've had some video montages together on megavideo. They are still going strong with up to 4 songs in each one. It's kind of slow to upload, and it takes a few hours after that for them to convert everything, but after they have been great.
Although I am sorry to hear about your YouTube video, I am glad to see that you are amongst the living. I was beginning to wonder where you had gone off to!