Is it possible to run rmiregistry on a different machine than the remote object? How is it possible for remote objects running on different machines to "share" a common registry?

I'm afraid the answer to your question is no. rmiregistry must be running on the same computer than the RMI server

If you need to be able to run a service directory (an equivalent of rmiregistry) on a different computer than the one where you server is running, you should consider looking at CORBA instead of RMI (but CORBA is more complicated and will cost you money)