Well, did you install the key in the container named key in the crypto provider on the server? See How to: Use the X.509 Certificate Management Tools.
BTW, if you are able to decrypt on your machine something that should be a private key only on the server, that key is already compromised. You should change your keys asap.
After your Update
RSA cryptography is based on assymetric key. You encrypot with the public key, the destination decrypots with the private key. The keys are provisioned upfront, the destination of your generates or obtains a key pair and keeps the private part to himself and advertises the public part for others. Usually the keys are packed as X509 certificates because this utilizes the whole trust infrastructure around certificates (signatures, trusted authorities, certificate purpose etc etc). In that case the destination of the message must requests a certificate for encryption purposes from a trusted authority (ie. Verisign) etc etc. Or use a self signed certificate (makecert.exe) and establish the trust by some out of bands methods (ie. a phone call to validate the certificate hash or IssuerName/SerialNumber).
RSa cryptography is very far from 'just strings'. Closer to 'just strings' is symmetric key cryptography (AES, DES, XDES, RC4) where your application has a secret key used both to encrypt and decrypt.
Now, unless you really know what you're doing, steer clear of cryptography, use an off the shelf protocol like SSL/TLS (online) or S-MIME (offline). Better still, use some framework facilities like CryptoStream or ProtectedData. Don't create yet another pseudo-encryption based on newsgroup advice from people you never met...