I have exactly similar problem too. I have used the command
findprivatekey root localmachine -n "CN="CertName"
the result shows that the private key is in c:\ProgramData folder instead of C:\Documents and settngs\All users..
When I delete the key from c:\ProgramData folder, again run the findPrivatekey command does not succeed. ie. it does not find the key.
But if i search the same key returned by earlier command, i can still find the key in
C:\Documents and settngs\All users..
So to my understanding, IIS or the hosted WCF is not finding the private key from C:\Documents and settngs\All users..