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