FileIOPermission CreateDirectory does not work as expected

There appears to be a recent issue with how CreateDirectory resolves FileIOPermission that is causing issues on our server.
Reading through some similar posts on the issue there is a lot of misinformation being given out, so I am hoping to get some kind of clarification.
Given the following setup:
1. Windows Server 2003 SP2 running IIS6 with latest version of .NET Framework 3.5 SP1 fully patched
2. A web site created under IIS6 running under Medium Trust and with the Network Service user being given Full Control over the virtual directory.
3. Running System.IO.Directory.CreateDirectory with the following code:
System.IO.Directory.CreateDirectory(Server.MapPath("~/testfolder"))
4. Fails with:
[SecurityException: Request for the permission of type 'System.Security.Permissions.FileIOPermission, mscorlib, Version=2.0.0.0, Culture=neut ...