Please give us an execution plan for both the full update, and for the following SQL
SELECT oms.addr_id
FROM hr.addresss_oet OMSS,
hr.master_address oms
WHERE NVL (oms.addr_line1, '-1') = NVL (OMSS.addr_line1, '-1')
AND NVL (oms.addr_line2, '-1') = NVL (OMSS.addr_line2, '-1')
AND NVL (oms.city, '-1') = NVL (OMSS.city, '-1')
AND NVL (oms.state, '-1') = NVL (OMSS.state, '-1')
AND NVL (oms.pstl_id, '-1') = NVL (OMSS.pstl_id, '-1')
AND :b1 = OMSS.ADDR_KEY
but there's a good chance the SQL statement above will be run for each row in the source table, so if that SQL is slow, then it will be "slow x n" where 'n' is the number of rows that need to be considered.
That inline select suggests you have no true correlation between the two tables, just a concatenation of potentially not-null fields.
If this is a one-off exercise, you could consider putting a hash key on each table as a virtual column, for example
hash_key generated as
ora_hash(addr_line1||':'||addr_line2||... pstl_id)
and then index oms on that hashkey, and omss on ( addr_key, hashkey)
to give good selectivity into each table.