Well I created a test database with 300,000 rows (yours had 160,000) and still didn't encounter this problem on an UPDATE. That said, our server is using a much later version of MySQL than yours is. There have been quite a few MySQL bugs (not VaultWiki bugs) which caused 'can't find record in' messages that have been solved by its devs, but it's hard to say whether this is simply an update-MySQL-to-solve issue. For example, one of the bugs displayed that error message when a result set could not be found within the MySQL timeout limit. So I started looking into speeding up this UPDATE.
I did notice that performing UPDATEs of this sort on an InnoDB table with 300,000 rows started to get slow (roughly .24 seconds for me).
Changing the table engine back to MyIsam seemed to speed it up (.17 seconds). I think this is because of the number of indexes on the table, and InnoDB isn't optimized for that.
Once in MyIsam, I checked how FULLTEXT would perform, the results were over 1 second.
I reverted back to the current INDEX and reduced the key size by half. The query now took about .01 second.
This seems to be an acceptable increase to me, although it means some links won't be updated correctly if they don't differ in the first 125 characters. Perhaps this is an acceptable loss of functionality for the performance gain. Plus it can be worked-around by using a SELECT, check for match in PHP, UPDATE method.
To slow the growth of the size of vault_link, auto-links should not be cached, only intentional links.
In order to avoid similar problems scaling categories, articles, protection, likewise changes should be made to those tables. Also, the type index on the vault_link tables are not optimized. Should change to using content-type IDs to significantly reduce the key size.