I've found that on some websites, the links weren't rewritten, most likely because of delayed results fetching, for example in search engines like Searx.
Perhaps a simple delay of rewriting would do in most cases, without being annoying.
// Get the Invidious instance to use for rewrite
setTimeout(() => {
GM.getValue('YT2IConfig',JSON.stringify(defaultConfig)).then(function(result) {
rewriteLinks(result);
});
}, 2000);
A wholly different approach could be to rewrite only when a link is clicked. This will probably create a few compatibility issues to be mitigated, although I've been using code like this for (optionally reviewable) direct links in Gmail for quite a while (but that's just one site).
document.addEventListener('click', e => {
~"if the URL doesn't contain any of the to be rewritten websites"
return;
e.preventDefault();
location.assign(rewriteLink(e.target));
}, true);