It much depends on what you're up against (your scenario).
A "normal" user could be trusted with a headless machine and a closed Linux installation, just closing off GRUB. This and a suitable contract/license would suffice. You can disconnect keyboard and mouse from the motherboard, seal the unit and only export your service and SSH.
The next level is disk encryption - a more sophisticated but still wet-behind-the-ears guy will just try to mount the disk from another machine, and might not even be aware there's such a thing as a ext4 or a NTFS - possibly "The disk must be formatted!" will be enough to scare him off, or he'll try with a extfs reader and won't be able to access the encrypted partition.
This is more or less where you'll want to stop. Going further adds complexity and still can't achieve total security.
The next level is a user savvy enough to understand that if the disk is encrypted and yet it boots, it means that the boot sequence has access to the decryption key. I've heard of experimental drivers (mainly working through obscurity) that hide the key in strange places, from unused CMOS memory to external EEPROMs, but as the old joke goes, we've already established how this will end, now we just haggle about the price - how much effort will be needed by a determinate hacker with full hardware access to break in. For if he's determined enough, he will break in.
There are drivers (and undetectable hardware devices, and virtualization methods) that allow intercepting both parallel port and USB traffic. Controlling the hardware clock and I/O, a replay attack becomes possible that will allow booting into a tampered system, thereby either allowing access to the decrypted disk from the "outside" of a VM, or starting extra services that will allow the same. So you would need to add sophisticated self-checking mechanisms to prevent this.
At this point, check out answers to the new problem and consider using a specially designed PC where the hard disk can't be removed. Keep in mind that "can't" means that you and I couldn't, but
Chuck Norrissomeone (again: determined enough, wealthy enough, knowledgeable enough, ruthless enough) can.
Something you might try (and it still does not supply complete security) is to require that the machine is always connected to the Internet. Yes, the data is secure inside and doesn't get out, but when it boots, the machine can access an external server and get its decryption password from there using a scheme resistant to replay attacks.
Of course, if you're up against a determined hacker, one day the machine connecting to your server will not be the actual machine but a subverted piece of code that will (try to) steal the decryption key. With some luck, however, this will not succeed on the first attempt, and in the keyserver logs you'll see a sequence of a few reboots and key requests while the guy drills through the defenses.
Another possibility would be to allow the user to enter a response to a challenge via SMS. This would guarantee the customer that the server can't exfilter anything, and you would still have some sort of pulse on the situation.
Another possibility that occurs to me is that the user's PC contains their data, but it does not contain your service. This is downloaded directly to memory securely from the Internet, and executed at each boot. You would need a "supervisor" application that examines its environment and determines it's secure and untampered-with, and then requests through SSL and presenting a license key the latest application binary from your server. The binary downloads and starts doing what it needs to do on the data in the target PC, never being saved to disk.
The server can verify the caller's IP address if belonging to a known customer network.
Now the attacker has to fool the supervisor application (which will still connect and request a binary even if it detects a tampered environment. It will just do so including a subtle hint that it's acting under duress - a "hawaiian good luck sign" if you will), and unless the attacker is the customer himself, also fool the server as well as seize the computer. Still possible, mind you, but way harder.