У меня нет MySQL, но это должно работать:
UPDATE TargetTable
SET key = CONCAT
(
SUBSTRING_INDEX(key,'_',1)
,'_'
, (SELECT newsiteid FROM MappingTable WHERE MappingTable.oldsiteid = SUBSTRING_INDEX(SUBSTRING_INDEX(TargetTable.key,'_',-2), '_', 1 ))
,'_'
,SUBSTRING_INDEX(key,'_',-1)
)