Answering the question after "solving" the issue, for the record:
We found out that by error, the system was asked to geocode by "address, state, USA" but the city wasn't included.
All the information that you can always add in the addresss will be useful for sure. In this case, adding the city name is something critical, as there may be a lot of streets with the same name around a country.
I usually like to do something else. Although CartoDB concatenates adequately the different columns, I always build a column and add all the data in that unique cell. You can do this with a query like:
UPDATE tablename SET new_address_column = street || ', ' || city || ', ' || zipcode || ', ' || state || ', ' || country
This way you can check directly what you're going to send before doing it. It's really important to take care of the data a little bit to avoid surprises afterwards! :)