The Trusted Locations business is just Excel assuming that stuff on your own hard drive is safe, but that stuff on a network is questionable. It sounds like you've figured out how to reassure Excel on that issue.
If you customize the NodeXL template file, or any other Excel template file for that matter, you have to be careful how you open the template file to add your customizations. Here is one correct way:
1. Open Excel.
2. Use Office Button, Open to open the NodeXLGraph.xltx file. The file opens as a template, which is what you want.
3. Add your customizations.
4. Save the NodeXLGraph.xltx file.
If, instead, you double-click the NodeXLGraph.xltx file, for example, Excel will create a
workbook from the template instead of opening the template itself. You don't want that during customization.
Because your end users will be double-clicking your customized NodeXLGraph.xltx file or using a similar technique, Excel will create a workbook from the template (which in this case is what you want) and not simultaneously editing the template. I think
that should work with no problem.
Whatever you do, give yourself plenty of time to get this all set up. As you said, you don't want any last-minute surprises.