How can I secure my plugin so only paying users can use it?

If your plugin relies upon interaction with your own server an API key is an excellent way to prevent non-paying users from using it.
However if it doesn't need to interact with your server then anyone with a little PHP knowledge can modify your plugin to remove the API key check.

A major issue here is the licensing for your plugin. WordPress is GPL, and the GPL has a clause which requires 'derivative works' to also be licensed under the GPL. (That's an understatement: in fact, the whole GPL is based around that clause and wouldn't really work without it.)
There is a lot of argument about whether a plugin can be considered to be a 'derivative work'. In my opinion it isn't, and I think it is unethical to try to force it to be seen as one. However Automattic, the core WordPress devs, and the Free Software Foundation (the organisation which wrote the GPL) claim that WordPress plugins are legally bound to use the GPL and may not use another license.
So far there have been no court cases and so there is no precedent, but there is considerable animosity surrounding a couple of major WordPress plugins which don't use the GPL, and Automattic has basically threatened legal action whilst the plugin developer has said "please sue me". Not exactly a pretty situation, and I would say that regardless of the morality of the situation the fact is that the negative publicity normally outweighs the benefits of closed-sourcing a plugin.

To summarise: your plugin basically has to be GPL, which means you have to provide unencrypted source code, so anyone can modify your plugin to remove any restrictions you add. But it should be easy for you to talk most of your potential customers into wanting to buy the plugin from you instead of using a forked version - you can offer benefits such as support, upgrades, etc etc which probably won't be available for a "cracked" version.

There are several companies which successfully sell plugins, under the GPL and with no protection (API key etc). Even though anyone could in theory just download the plugin and upload it to a public site from which anyone could download it, in practice nobody wants to use an unofficial version which won't necessarily be updated for new versions of WordPress. So selling plugins does seem to be a viable business model even without protection of any kind.

Of course, all this assumes that someone doesn't just fork your plugin and carry on maintaining the codebase separately. There's not much you can do about that - but it's unlikely to happen.

For what it's worth, if you're trying to make life hard for someone who decides to redistribute your plugin, you may like to consider the following :

• you can still claim trademark rights on the name of your plugin even if the plugin itself is open source, so you can legally prevent them from using the same name which your customers know
  
• only the PHP code in a plugin has to be GPL'ed - you can distribute any files which don't contain PHP which interacts with WordPress under a separate license to forbid redistribution. For example, CSS, JavaScript, and images don't have to be under the GPL.

Using an API key is probably fine. You can't worry about people pirating your plugin, because it will happen no matter what you do. Someone with the knowledge to remove your API check is smart enough to remove any kind of protection you put in your script. You can't worry about these people.

Using products like Zend Guard isn't an option. It requires the end user to have Zend Optimizer installed on their system, and you can't guarantee that.

All that being said, you can't obfuscate or otherwise hide your source code anyway. Wordpress is licensed under the GPL license, and they strictly forbid plugins from having any other license. While you can sell the plugin, you can't hide the source code.

A great article can be found here, although this doesn't cover technique just somethings to bare in mind before you pursue the route much further http://www.littlehart.net/atthekeyboard/2007/07/20/protecting-your-php-code/

Although for a more direct answer to your question, use an API key system and then encode your PHP using something along the lines of Zend Guard, so the user can't just go in and remove the API key check as the code is encoded.

to be honest, i don't think there is a bullet proof to avoid your plugin to get nulled, look at WProbot, they have a pretty solid way to validate licensing but still there are hundreds of nulled versions.

as long as people have to download your code someone will get his hands into it and nulled it, what you can do is offer a fremium version like s2member and AllinOneSEO pack does.