Todd
Only one other thing that makes any sense to me...
Your templates, if I am correct, you probably select from a list of some sort, rather than the standard Outlook "File/New" option for the new mail message.
Seeing as other messages are saving and the templates are not, this must mean that the "Save messages to sent items" is indeed selected within the Tools/Options/E-Mail options.
Thus the problem would exist within the templates. The templates would appear to have the standard type of Outlook habits as far as sending is concerned, except one...save to sent items.
I have not yet had to physically work with templates, but you can check the following as well.
In the forms "Design View" select Options to activate that forms options (message options) and check that you have selected to "Save sent items to: Sent Items"
Unfortunately this is all else I can think of.
Will continue the search though.
Hope this helps