I've been toying with this lately. My requirements include Python 3.x which immediately takes solutions like Jython and IronPython off the table. I'd be hesitant to take that route anyway, as I've never trusted user-mode language VMs.
That being the case, for my purposes the best solution so far is to take it out of the hands of the interpreter completely and run in a strongly locked-down container (OpenVZ or similar). However, this is taking a hammer to the problem (albeit not the sledgehammer of full virtualization), and may not be viable if you have to run a truly huge number of isolated interpreters.
One upside, though, is that because it doesn't rely on the security of any particular interpreter, you can use any arbitrary language you want in the environment -- you don't have to tie yourself to Python or the set of languages/implementations available for JVM or .NET/Mono.