I want to encrypt the same message multiple times. I want to store the encrypted messages together. I've heard if you do this with RSA, an attacker could decrypt the message with the Chinese Remainder Theorem.
What encryption methods do not suffer from this vulnerability? Would RSA with some random bits added to the message suffice?
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.
