Yesterday evening I was trying to use the soul package with XeLaTeX but it did not work. More specifically, the command \ul did not work with Greek texts. I did some google search and I found a way to make the package usable with XeLaTeX. In the preable of your XeLaTeX file add the following commands:
\makeatletter
\font\SOUL@tt=”[FreeMono.otf]”
%\makeatletter\font\SOUL@tt=”Consolas”
\setbox\z@\hbox{\SOUL@tt-}
\SOUL@ttwidth\wd\z@
\makeatother
One needs a monospaced font that will be used internally by the soul package. Here I am suggesting the use of freemono but one can use any other font that contains the script you intend to use in a document. If the font does not contain glyphs for the script one plans to use, then the package will not work at all. It sould be a good idea to create a package but since the solution depends on a font, it cannot be a generic solution.