How can I securely encrypt the same message multiple times?
No, "RSA with some random bits added" does not suffice. There have been attacks against many of bad padding techniques for RSA. Instead a known secure mode of operation is required. The most well known secure mode is RSA-OAEP.

The earlier RSA with PKCS#1 v1.5 padding may also be secure, but it has a well known attack against it called the Bleichenbacher attack. More to the point, there is also a million messages attack which shows one example what kind of attacks is possible if you just "add some random bits" to a message.



Note that the security argument of RSA-OAEP was under serious scrutiny. This has weakened but not broken the security proof for RSA-OAEP, which had to be adapted to the new situation. Furthermore, implementation mistakes may allow attacks against RSA-OAEP.

This is why there are some proponents here for RSA-KEM. Here RSA simply encrypts a random number in the range $[0, N)$, which is then fed into a key derivation function or KDF, which in turn creates a secret key which can be used for symmetric encryption. This is a rather elegant scheme which is provable secure, just like OAEP.



Note that the security proof for RSA-OAEP and RSA-KEM assumes that the RSA trapdoor itself is secure. However, that's something that cannot be proven - we just assume it is secure because it withstood all attempts so far.