I used the Microsoft Decoder also for more than a year on Vista, but since I run Windows 7 or 1.1 Alpha I have this problem.
Will wait for somebody else than that also has that problem.
Yes, it is possible that some of the graph clean up fixes we have done lately has been fixing the issue you were seeing. It was just most likely a bad luck that only you seemed to have the locked file issue (timing based bug).
FWIW, my system has done that occasionally ever since I've been using MP (various versions since about 0.2). Sometimes it won't delete recordings after watching them, but will do it eventually so it's never really bothered me enough to do anything about it. Sometimes it takes a long time to "release" whatever's causing it - even after several complete reboots - so I just keep trying every now and then and it'll delete it in the end (sometimes quite a few days later). It doesn't happen every time, only rarely.
So tCC isn't the only one to get this - perhaps he's just more fussy than the rest of us
OK, next time it happens on my system I'll try to remember to post logs. It doesn't happen very often though, so it could be some time (I reckon it only does it once every few weeks).