Deny and PermitOnly cannot be used to create an effective sandbox because like Assert, they function as stack walk modifiers -- meaning they modify the current call stack and not the grant set of an assembly. We talked about this previously in Assert Myth #1.
For instance, lets look at an application App which attempts to sandbox AddIn via Deny. (With the call stack growing up):
Notice that AddIn still has FullTrust, although there's a stack modifier in play here. In this case, the demand will inspect AddIn.Run and succeed. It then moves to App.RunAddIns, sees the Deny, and fails.
Now, suppose the author of AddIn doesn't like this situation very much -- they'd actually love to be able to access the file system. So they've decided to update their code to Assert for FileIOPermission:
Now the stack walk checks AddIn, and does not fail because it's FullTrust. Further, there's an Assert for FileIOPermission, which causes the stack walk to terminate. Since the security system didn't encounter any stack frames which failed the permission check, no SecurityException is thrown. The Assert prevented us from ever seeing the Deny. (The same analysis applies for PermitOnly).
Even without taking Assert into account, Deny and PermitOnly aren't effective against LinkDemands. Process has a LinkDemand for FullTrust. Presumably you don't want your sandboxed code using it. However, the LinkDemand is only going to check the immediate caller, which will succeed since the grant set is unmodified. Since there is no stack walk, the Deny is never encountered.
In order to effectively sandbox code, you need to create a sandbox AppDomain which causes the grant set of the assembly to include only those permissions you wish it to have. In v1.x this was complicated -- so in v2.0 you should use the simple sandboxing API.
So what use are Deny and PermitOnly if they can't be used for sandboxing? Using them allows your code to apply least privilege to itself ... to say "I shouldn't ever be touching a file in this code path, so I'm just going to deny that permission to myself". Since you're not trying to sandbox here, the ability to step around the Deny doesn't hurt you. However, doing this for all call stacks can be, to say the least, burdensome. Most code that reduces its permission set for least privilege purposes tends to use an assembly level RequestRefuse, or simply sandbox themselves.
Deny and PermitOnly can also be used for testing. If you want to write a unit test that says "this API should only require permission X to run", you could do a PermitOnly and call into it. The same could be done with Deny, this time testing "this API should require Permission X or it won't run".
If you run FxCop over your code, this information is wrapped up in rule CA2107: Review deny and permit only usage.