I've got project in production which is similar to your scenario. I have a Windows Service hosting endpoints via netTCPBinding and I used x509 certs... although in my case, the intent was to encrypt both the transport and message layers, as I was crossing over untrusted security boundaries. I was less concerned with providing authentication/authorization other than requiring the certificate be present.
Similar to your intranet scenarios (I'm assuming), I had authority over the server and client machines at installation time... or at least could dictate some of the terms of installation.
Rather than purchase the x509 certs and burden the client with that expense, I opted to roll our own. We set up one of our Win2003 servers to be a CA, issuing our own Certification Authority cert. We then generated an x509 cert for the server, as well as individual x509 certs for the clients.
The client and server certs were installed on both clients and server (as appropriate) into the personal user store at the computer level. We also installed our CA cert directly into the Trusted Root Certification Authorities section, thus making our client and server certs trusted.
Because I was less concerned with authentication/authorization, I don't know what to recommend as a best practice for dealing with binding certs to individual users and going more granular than machine-level (my solution was windows service to windows service communication -- completely unattended). I would think you'd need a cert for each user, installing it into their personal user store in the certificates MMC. The runtime implementation will be guided by how you configure WCF to do the cert lookup, so it should be fairly easy.
Throughout the process, I relied heavily on what I'd learned from this great CodeProject article: Securing WCF Services with Certificates. It walks you through generating/installing the certs. The sample WCF applicatoin is IIS-hosted, but I was able to pretty easily translate the config sections from web.config to app.config.
In my case, I exposed the Web interface for requesting certificates in Win2003 to the web itself, so the client could request certificates directly in the future. We have approval control, so it works well. I haven't had a need to generate new certs yet, so I can't say how much friction that would entail.