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.
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.