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.
http://blog.heroku.com/archives/2010/9/20/an_update_on_herok...
And Joyent's Node service is pretty good too:
https://no.de/