I've used the following formula in Visualforce email templates to generate the server instance for a link:
Left($Api.Enterprise_Server_URL_190,(find('/services',$Api.Enterprise_Server_URL_190)))
Then I just concatenate the record id to this
Note: this was for eu server instances, though I can't see why the NA etc would cause a problem.
If this can't be used, due to an HTML template for example, you can create a custom formula field on the sobject, called Record Link or similar, as follows:
HYPERLINK(Left($Api.Enterprise_Server_URL_190,(find('/services',$Api.Enterprise_Server_URL_190))) + Id, 'Record Link' )
and then use that in the template.
If this is still pulling the custom web address, you may need to revert to the clunky mechanism of storing the server URL in a custom setting and use that in the email template. The downside to this is that whenever you refresh a sandbox (for example) you'll need to fill in the custom setting anew.
So if I have a custom setting named 'URLS' and this has a field of 'Server__c', I can use this in the template as something like:
Direct Link: {!$Setup.URLS__c.Server__c + '/' + id}