Creating a PHP API: Checking from which server the API Request comes from

I'm creating a PHP API for a website and I'd want to restrict the API access to domains that are registered on our server (in order to prevent abusing of API usage). So, this is my approach right now, and well, it should look pretty good on paper.

1. The API is setup at api.example.com.
2. A user that wants to use the API registers with us, adds his domain and gets an API key.
3. The user of the API will use his API key to encrypt his request data (via mcrypt) and sends it, via cURL to api.example.com.
4. My server checks from which domain this API request comes from and matches that domain to an API key in the database. If there is an API key, the API decrypts the request via mcrypt with that key and then using the same method encrypts and sends the result.

I'm stuck on step 4. Originally, I planned to use HTTP_REFERER to check it, but since cURL doesn't send one by default and it could be easily faked in the user-side code (CURLOPT_REFERER as far as I remember), I am stuck here.

Is there a method to know from which domain this API request comes from? I see that it can be done with some popular APIs like the reCAPTCHA one. Checking the _SERVER["REMOTE_HOST"] isn't really an option because of shared hosts (they have the same IPs) so this would not be able to prevent abuse (which would originate mostly from shared servers anyway).

Is there such a method to check for it? Thanks!