I had a similar issue deploying a SLSB as webservice and recognized, that my ear has a lot of jars (including saaj) in the lib directory.
After clean up the ears lib to include only my application jars, the ClassNotFoundException isn't thrown anymore!
Maybe this is a hint for solving your problem.
Kind regards
Willi