You want a public-private key infrastructure
From your question you seem to be looking at a public-private key infrastructure (PKI). The ID your client sends is their public key and is totally free to view by anyone. Your servers encrypt the data using a combination of your private key and their public key. This encrypted payload is then sent back to the client. They then use their public key and private key combination to open it. They know it can only have come from you because your private key has signed it to say so and they trust that only you have that private key.
You want to make sure that your clients look after their private key, but that's a matter for them and their operating system.
For a general overview of how PKI works, Wikipedia has a nice article about it. For exact details of an implementation, see OpenPGP in RFC 4880.
Google Keyczar offers a nice and simple API approach to PKI. You can easily generate secure server-side public and private keys and update them if an older one becomes compromised. They don't handle key distribution, but it gives you a starting point.
Updated in light of revised question
If the client attempts to submit their own encrypted data it can only have been generated by their own private key. This will fail the signature test on your servers since you will only accept encrypted data created from your own private key.