On one of our internal mailing lists, someone was recently surprised that calling RSACryptoServiceProvider::Encrypt on the same bytes with the same instance of the RSA object resulted in two completely different output bytes arrays.
The reason is that RSA uses random padding on the input bytes, either OAEP padding if the second parameter to Encrypt is true or PKCS #1 v1.5 padding if it is false. Both of these padding formats are documented in PKCS #1. (you’ll find OAEP in section 7.1 and PKCS #1 v1.5 in section 7.2).
If PKCS #1 v1.5 is used, the data that is encrypted is actually:
0x00 | 0x02 | random non zero padding bytes | 0x00 | original message
OAEP works similarly, attaching padding that contains some random data to the original data and using that as the input to the encryption function. In either case, since the padding is applied before the data is encrypted, it can affect all of the bits of the output. This explains the original behavior — encrypting the same data twice with the same key ends up with dramatically different results, however the results all decrypt to the same expected value.