Server side JavaScript cleanup or sandboxing?

I am looking for users to be able to enter JavaScript to specify some logic in my application. JavaScript will be injected and displayed in the browser, but first it will be saved and validated on the server side.

This opens up obvious security implications.

Ideally, I would like to only allow a subset of the JavaScript language. Intuitively, a choice approach - indicating what is allowed and giving up everything else - seems safer than a denying approach - indicating what is prohibited.

A lot of the solutions I've seen are client-side - I think a server-side solution makes more sense for my needs as I can give feedback to the user if the JavaScript is invalid and only save it to the server after it's "cleaned up".

It would also be helpful to create something to parse JavaScript and do some checks - for example, I would provide the user with some variables, I would like to check that they are not using any uninitialized variables, or that the code returns something in the expected format ... A sandboxing solution should at least not get in the way of this, but it could potentially actively help - if it works by parsing code, not just regexes, and I can put my own hooks to check some syntax.

Google Caja looks like it can do what I want, but I didn't dive into it very much.

What approach would you recommend?

Excellent open source solutions. I don't mind writing my own code, but it seems like a non-trivial problem for a correct solution from scratch.