"I'm using [AES] in CBC mode, but the implementation doesn't add the randomness I want, the same message when encrypted looks the same."
This is a problem. If you were using CBC mode correctly (i.e. with a random IV), then encrypting the same message twice would produce completely different ciphertext.
Since you're not using CBC mode in the way it's supposed to be used, it can leak information to an attacker. There are several different ways in which this can happen, but the obvious one, which you've already noted, is that using CBC mode the way you're (mis)using it will reveal whether two encrypted messages are the same or not. (In fact, using CBC mode like this will also reveal whether two message share a common prefix of at least 16 bytes, and approximately how long any such common prefix is.)
Fortunately, the fix is simple: as long as you choose a random IV for each message (using a cryptographically secure random number generator), CBC mode is provably semantically secure as long as the underlying block cipher (AES) is unbroken.
Alternatively, if you don't trust your random number generator to be secure (which may be a reasonable thing to doubt; it's hard to verify that a RNG really is secure, and there have been some notable cases where a supposedly secure RNG actually turned out to be completely insecure), then you can instead take a unique message identifier and encrypt it to generate the IV. Or, equivalently, you can use a fixed IV and prepend a unique plaintext block to each message.
Ps. Note that, in any case, CBC mode encryption alone will not protect your encrypted messages from modification, or from attacks involving forged or modified ciphertext (like the well known padding oracle attacks). To be safe from such attacks, you really should include a message authentication code (MAC) with your messages, and verify it before attempting decryption. Or, alternatively, switch to an authenticated encryption mode that combines encryption and message authentication into a single operation.