I have the same problem as BungyCase, as of yesterday. I've followed all the instructions you laid out, Linc, but to no avail. Still get the blocked plug in message. I also get it when trying to listen to BBC4 extra programs... not video. (This is where I noticed the problem first.)
Since I'm not getting the "missing plug in" I didn't follow those instructions, but did explore them.
I went to the Flash site and it says the latest version I should have is 15.0,0.189, but when I checked my system preferences, after installing the latest version 5 times and relaunching Safari, it says I have 126.96.36.199 installed. So... does that mean anything?