This answer had two parts:
As detailed in my Update #1, you have to put your suggestion last in the theme_hook_suggestions array, as last is highest priority.
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