That is a valid approach.  I suggest that one remember what it "means" to have
an exception, what it means to throw an exception, and the prime importance of
operations, particularly relative to development.  Jan's answer typifies this
deep understanding - notice the emphasis on what the *contract* of the
interface is, and the acknowledgment that that contract is by design.
Whatever the implementor does, it must not violate that contract, so it
behooves the author of an implementation to understand the semantics of the
contract.

Throwing a runtime exception in turn is also a signal to client code of the
rethrower.  It tells that client code that it made a mistake, under the
programmer's control.  "Tsk, tsk, you should not have given that illegal value
(IllegalValueException)."  This type of error is for the client programmer, to
help them debug their code.

Checked exceptions tend to be for things the programmer cannot reasonably
control, like the file being deleted by an external process or the certificate
repository suddenly becoming unavailable.  That's why the API designer placed
those exceptions in the contract for the method.  Because the client
programmer cannot control these events, the API designer ensures that they
must check for them.  Logging for this type of exception is vital - it helps
the sysadmin understand the operational fubar and fix it.

Often the semantics of a method that returns a String [], as in the OP's
situation, or equivalently a Collection<String>, disregard the reason why
"nothing" is retrieved.  All the client code really cares about is if anything
came back.  An empty set is empty whether the database is down or the customer
never shopped there, who cares which?  Either way the situation could be
different by the time of the next query.  In that case, a value like
Answers.EMPTY (a final value from a hypothetical Answers class) defined as a
String [0] or an unmodifiable new ArrayList<String>(0) would be the sentinel
value returned.

Rethrowing an exception does not, under the Sun JVM, clear its
stacktrace:

public class Foo {
   public static void main(String[] args) {
       Handler h = new Handler();

       try {
           throw new Exception();
       } catch (Exception e) {
           h.handle(e);
       }
   }
}

class Handler {
   public void handle(Exception e) {
       try {
           throw e;
       } catch (Exception ee) {
           e.printStackTrace();
       }
   }
}

//--

Prints:

java.lang.Exception
    at Foo.main(Foo.java:6)

The stacktrace is actually populated when the exception is created;
one of the problems with creating an Exception object in advance is
that the stacktrace will not indicate where it was thrown!

There are some clever uses for this behaviour that I will leave it to
you to discover. :)

...

That works for single exceptions (and it's probably how I'd do it
under the constraints), but not all services only throw one type of
exception that's more specific than Exception.  Other approaches are
necessary if you want to make the exception handler interface specific
to the exceptions that can actually be thrown, for these services.

-o