Caller ID for SMS doesn't recognize contacts unless I add the country code to all If I have a contact with the number 099123456, the caller ID doesn't recognize it, I need to change it to +59899123456.

My phone is a Galaxy S2. I have friends with other android phones (Galaxy S1, Nexus S) and the same carrier, but they don't have this problem. Could it be some kind of setting?
It's always a good idea to save numbers in canonical format, this ensures that you will be able to call the contacts if you are roaming in an foreign country.

You issue is surely related to the Android ROM you are using. You could try to use another ROM. But as I stated before, saving the numbers in a canonical format will be the best solution.