This answer had two parts:

1. As detailed in my Update #1, you have to put your suggestion last in the theme_hook_suggestions array, as last is highest priority.

2. I'm not sure why, but your template files must be named with two dashes, not one.

File system:

node--taxonomy.tpl.php

As added to theme_hook_suggestions array:

node__taxonomy

This answer had two parts:

1. As detailed in my Update #1, you have to put your suggestion last in the theme_hook_suggestions array, as last is highest priority.

2. Your template files must be named with two dashes, not one.

File system:

node--taxonomy.tpl.php

As added to theme_hook_suggestions array:

node__taxonomy

Well, one answer is to force it to just look for your template specifically:

if(arg(0) == 'taxonomy') {
  $vars['theme_hook_suggestions'] = 'node_taxonomy';
}

I have no idea if this is a bad idea and against best practices. Any one?

This answer had two parts:

1. As detailed in my Update #1, you have to put your suggestion last in the theme_hook_suggestions array, as last is highest priority.

2. I'm not sure why, but your template files must be named with two dashes, not one.

File system:

node--taxonomy.tpl.php

As added to theme_hook_suggestions array:

node__taxonomy