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.