WPF MediaElement problem

Your explanation is clear (well, thank you, this is so rare!). At the same time, we don't know what that 3rd-party application does exactly. Do you know? What exactly this 3rd-party application does to the same WMV file you try to use in your MediaElement?

It looks like your third party application locks the same WMV file by opening it with exclusive access options and keeping file handle opened.
If you're really sure the right media file actually exists in both cases, your exception message is misleading. It happens in some cases.

You can validate directly if this is the case with the following code (when your 3rd-party application is running):

StreamReader reader = new StreamReader("myMediaFile.WMF", false);
reader.Read(); //just one character
reader.Close();

If the file is locked by your third-party application, this code will throw exception.

You can test it from the other side: lock the file by some application, then try running your WPF application with MediaElement to see if it throws exactly same exception.

Please post your steps and results in comments to this Answer. Be prepared to output a complete exception dump (completed with full exception stack dump, with all inner exceptions, recursively) in some text file if more diagnostics is required.