The problem occurs when using the Microsoft.CSharp.CSharpCodeProvider type (located in System.dll) to compile source on the fly and generate new assemblies in memory. When CompilerParameters.GenerateInMemory is set to true, the CompileAssemblyFromSource method eventually calls down to Assembly.Load(byte, byte, Evidence), which has been obsoleted in .NET 4.
The documentation for that method states that when a null is passed for the Evidence, it will take the security permissions from the calling application domain. In fact, it takes the security permissions from the calling Assembly.
Now, I cannot use GenerateInMemory in a separate sandboxed AppDomain because no matter what permissions I give to the sandboxed domain the newly compiled assembly will bypass them and take those of the parent Assembly. At the very least, the documentation for the Assembly.Load method is incorrect.