Thanks a lot for the help, guys!
The issue was resolved yesterday after hours of testing.

All I had to do is to add a TRIM() to the Upper function. For example:
Via OCI (and in some cases SQLPlus), the first query does not return results in Ora 10g, but the second will always return the records expected.
Query with no results:
SQL> SELECT ENT_ID FROM ADDRESS_test WHERE
(UPPER(CITY) LIKE upper('Las%') AND UPPER(STATE) = upper('nv') AND SYS_DELETE_DT IS NULL )
OR (UPPER(POSTAL_CODE) = '99999' AND SYS_DELETE_DT IS NULL)
OR (UPPER(POSTAL_CODE) = '99999' AND SYS_DELETE_DT IS NULL);

Query with good result set returned:
SQL> SELECT ENT_ID FROM ADDRESS_test WHERE
(UPPER(CITY) LIKE upper('Las%') AND UPPER(STATE) = upper('nv') AND SYS_DELETE_DT IS NULL )
OR (UPPER(trim(POSTAL_CODE)) = '99999' AND SYS_DELETE_DT IS NULL)
OR (UPPER(trim(POSTAL_CODE)) = '99999' AND SYS_DELETE_DT IS NULL);

The problem is that these fileds are all VARCHAR2(100)/(20)/(50) and it looks that ORacle is treating them as CHARS... When I select the values from these columns, there are no characters appended to the actual value...
So, my question now is: how Oracle 10g applies the UPPER function compare to Ora 9i? Obviously 9.2.0.7 doesn't have this problem. Is this bug in 10g (all versions)?
Thanks a lot for the help,
mj