The reason you are getting the Access Denied error is because you can't just delete files from that folder. They are virtual paths to real files. There is probably a better way to do what you are doing.
Here is an alternative that I found here. It uses WinAPI, which is never fun, but it works.
//you'll need to add this.
using System.Runtime.InteropServices;
[DllImport("shell32.dll")]
public static extern void SHAddToRecentDocs(ShellAddToRecentDocsFlags flag, IntPtr pidl);
public enum ShellAddToRecentDocsFlags
{
Pidl = 0x001,
Path = 0x002,
}
//then call this from your method
SHAddToRecentDocs(ShellAddToRecentDocsFlags.Pidl, IntPtr.Zero);