How do I override a default view template from another module? Drupal provides hook_theme(). But is there a hook_theme_alter()? I'm looking for something like hook_menu_link_alter(), which overrides hook menu entries, but for the theme. I want to modify a view hook theme entry so I can specify where to look for one of my custom templates. I am not interested in specifying it through the Views interface, since it look for the theme template inside the theme folder, and I want my template in a feature module.

I found hook_theme_registry_alter() and _theme_process_registry(). You can answer which one is the best to use and why.

Which of these keys should I modify in order to make the view pickup the template from the module?

If I put views-data-export-xml-header--richard-feeds-nokia-movies--views-data-export-1 in the feature, the View defaults to pick up views-data-export-xml-header.tpl.php. If I put that template in the theme layer, the view picks it up (even with the registry alter hook in place).
Your feature should implement hook_theme_registry_alter(). The use case you describe is exactly what that hook is for. The example code linked on the API page should get you started. The basic idea is to target the entry that corresponds to the entry that views_theme() is inserting into the registry, and change the template to match the one in your feature.