Backlinks from UUID hrefs
Ok, so this problem was being caused by the language prefix in our paths in conjunction with aliases. drupal_get_normal_path was returning aliases instead of node numbers, and it returned nothing when the path had a language prefix. Also found that the substitute function drupal_lookup_path only works for aliased paths. The final code replaces line 634 of search.module:

$path = drupal_get_normal_path($match[1]);


becomes

$clean_url = preg_split('!(^[a-z]{2})/!i', $match[1])[1];
if ($non_aliased = drupal_lookup_path("source", $clean_url)) {
  $path = $non_aliased;
} else {
  $path = drupal_get_normal_path($match[1]);
}


The search_node_links table is now being populated properly and the "What links here"/Backlinks views are working correctly.