On the same line of thought, we're working on http://www.erbix.com which provides Server-side JavaScript hosting (and a browser-based code editor) using the open-source Rhino engine.
To help SSJS in getting main-stream adoption, we've coded some apps, Erbix Forms and Erbix Blog, written completely in JS, which we've open sourced and launched in the Erbix App Store ( https://secure.erbix.com/marketplace ).
Joyent employs ryah. They've been around for 6 years, although I'm not sure how long they've been doing server-side JS (at least since they bought Reasonably Smart at the start of 2009).
I would definitely be inclined to go with the Joyent service since that's where Ryan Dahl (creator of node) works.
And Heroku pretty much rules this realm.
To help SSJS in getting main-stream adoption, we've coded some apps, Erbix Forms and Erbix Blog, written completely in JS, which we've open sourced and launched in the Erbix App Store ( https://secure.erbix.com/marketplace ).
If you have any feedback let us know.