Yes, this is a shame that they are treating you in this manner, but unfortunately many companies are not aware of the
TN nor are they aware that it is quick, easy visa at a low cost. Most companies have heard of the H1B visa and its drawbacks and immediately believe all visas are like this.
We have found when you are able to clearly explain the TN and its ease during an interview you are able to avoid the issues you describe.
Imagine being in an interview and be able to answer your employer's visa questions and concerns and to tell them that you can get the visa yourself and be working within the next 7 to 10 days. That's when an employer starts interviewing you on your skills and puts the visa concerns aside.
Good luck.