It seems like the kind of problem that is better dealt with by a compiler.
I haven't had too much experience with Domains, but I believe they are generally used for courser grain error handling (because it's a bit verbose to attach them all over the place). E.g., to catch most errors (it's no guarantee what 3p libs do to your context) generated in fulfillment of a particular web request.
Also, do any of the promises libraries solve the backtrace problem, and if so how do they do it?
You're right that you have to manage exceptions, which is difficult. The biggest problem I've had with Node is the runtime exceptions that crash the entire process because they go uncaught. To deal with that, I have the server automatically restart on failure - far from an ideal scenario of error recovery (and what I think you're referring to when you talk about sacrificing error safety).
The stack trace is a pain for those operations, and any error that occurs as part of "normal" javascript operation (e.g. ReferenceError) has to be handled like a normal exception, which makes the style inconsistent and therefore a bit harder to manage.
I think that the latest or upcoming version of Node is presenting a solution to this in the form of domains, but I'm not too familiar with it.