Removing old Block Handles in Matrix Field?
Tried it here and seems ok. Once you have deleted your field, are you saving your matrix block (top right button)?

If you delete the field then try to recreate it straight away (or any other field for that matter), it gives you the Handle "videoUrl" has already been taken. until you save the block. Once you save, you should be ok to recreate.

It does seem a bit buggy though as you need to save in between each action... Might need to see what the craft guys think.