What kind of exception are you throwing? Have you tried throwing a com.mendix.modules.webservices.WebserviceException in your java action? If you use those, it will return your own exception message instead of a generic internal server error.
Javadoc:
An exception that can be thrown by webservices published by the Mendix application and webservice calls by the Mendix application.
This exception can be thrown in custom java actions handling a published webservice call to show a custom soap fault.
In the constructor, use the public field clientFaultCode or serverFaultCode to indicate a client or server error.
Why are you throwing exceptions in the first case? I think 'not found' should be part of your protocol instead of an exception (because it is not an exceptional cause, but a supported case).
For example you could call an 'user exists' webservice before trying to retrieve the user, or you could return a user without name/ id if nothing was found.