We use our own exception class. If that's not possible you can always translate from Unicode to MBSC represented in the current charset – you usually need this text only for a short while and further conversion is not a question.
I would suggest deriving from std::exception and extend it to use your unicode string class. Deriving from std::exception gives you the benefit of doing a:
catch (std::exception&)...
as your last catch and have it catch any exception you might have thrown (and STL). Where as if you create your own base exception (and have your other exception derive from that) you would need to add another catch.
Either way I don't think it really matters but I prefer this style (obviously this wastes an empty std::string from std::exception but I don't think it'll make a big difference).
I think Peter Dimov's rationale as pointed out in the Boost error handling guidelines covers this well:
Don't worry too much about the what() message. It's nice to have a message that a programmer stands a chance of figuring out, but you're very unlikely to be able to compose a relevant and user-comprehensible error message at the point an exception is thrown. Certainly, internationalization is beyond the scope of the exception class author. Peter Dimov makes an excellent argument that the proper use of a what() string is to serve as a key into a table of error message formatters. Now if only we could get standardized what() strings for exceptions thrown by the standard library...
If you really want Unicode you could UTF-8 encode the exception message, throw in a BOM in the beginning so you can tell if the exception message is UTF-8, raw char, or other encoding when you prepare the message for output.