|It still seems you need to get shot of everything to do with Flash then re-install.|
Have you removed Firefox and IE addons? Sometimes the Firefox one sticks but there are ways around it.
I don't normally advocate registry cleaners but in this instance there might be a case for using one after Flash seems to have gone. CCleaner's registry cleaner is one of the safest but if you go that way I would suggest you remove "only the registry entries that are clearly to do with Flash".
Having said all that, perhaps I should have first asked what exactly happens when you try to play a Flash Video - presumably online?
Always pop back and let us know the outcome - thanks