I'm pretty sure this would be a time to use Mutex:
The Misunderstood Mutex[
^]
A Mutex is "kinda" like a "lock", but it exists across all .net processes. You can create a Mutex for the user as in the examples in the link above, or set it globally for the terminal service machine so all instances for all users can see it.
You want the first option. If the Mutex is not global then only each user can see their own. Make sure the program checks for the mutex on startup. If it exists: "Already Running", if not: Create mutex and start
Hope that helps
Andy