The thing to do is try to avoid the scan of the big table; give it something simple to look for.
I don't offer any guarantee, but something like this might work:
update DUNCANTEMP set DOESEXIST = 1
where TOID like '100%' or TOID like '500%
and exists (select 1 from OS_MM_AREA OMA with (NOLOCK)
where OMA.TOID = RIGHT(DUNCANTEMP.TOID,13))
That avoids applying a concatenation to OMA.TOID, so it should be able to use the index for the existence test, which avoids scanning teh big table. It may of course do a scan on DUNCANTEMP, but that's unavoidable.
Anyway, for future reference: please remember to post an actual execution plan (if possible; estimated plan otherwise) with queries about improving performance.
Tom