Option 1 - Process some data on your system
I wouldn't place all of the plug-in's processing on your own server, but pick one or two vital functions and keep them hosted on your system. Then require an API key for each site that uses the plug-in so that they can communicate with your server.
Option 2 - Encrypt stored data and require a hosted decryption key
Another alternative is a basic encryption setup - this is actually a system I've been toying with for a while, I just haven't bothered to deploy it anywhere yet. The code itself (to stay true to the GPL) is all plaintext just like you'd expect. However, all stored data (default values, plug-in settings, etc) is encrypted before being saved to the database. The trick here is that the plug-in on the remote system doesn't have the decryption key - in order to decrypt the data, it has to post its API key to your system which then responds with the decryption key. This can then be stored in a transient (temporary option) for a certain period of time before being flushed - that way you don't have a site hitting your server every 2 seconds during heavy traffic.
The downsides of this approach might outweigh the benefits, though (which is why I haven't deployed it anywhere yet). First of all, a savvy programmer can capture the decryption key and then they don't need your server any more. Or they could just flush out all the encryption/decryption hooks and run in plaintext. This is the advantage of open source for the user and the disadvantage to the developer who wants to distribute a free-but-restricted system.
The other downside is the dependency on your server. Storing a key in a transient lifts some of the burden off your server ... but if your site goes down for an hour or two, then every site using your plug-in goes down for an hour or two unless you plan for some kind of graceful deactivation. Also, it would mean you'd have to keep said server up-and-running indefinitely if people continue using your system.
Option 3 - Limit the features of the "free" version
A last option, and one I'm actively working on using, is to split your plug-in's featureset and functionality. The core of the system (UI, basic features, etc) is freely available without registration. For more advanced features, users have to register their copy, gain an activation key, then enter that key into the UI to complete the process - the plug-in then verifies with your server and downloads additional premium "add-ons" to the system.
The disadvantage here is that once downloaded, all the code now rests on the user's site and, under the GPL, they can still redistribute the full package. The advantage is that it only depends on your system once and doesn't require any kind of long-term download/processing support.
Any way you decide to move forward, you're either going to be hit with maintaining some sort of external API on your server or providing the full source of the system to your users. If you keep some functionality on your system, you almost have to guarantee 100% uptime for it to be worth it. If you're going to provide the full source, there's no way (under the GPL) to prevent someone else from re-distributing your system.