So the situation is that a company is interested on hiring me, as far as I can tell it is possible to apply for a TN visa while being legally in Canada (which is the situation), but I also heard that the consulate might not be able to verify my information to do so, how accurate is this?
As someone who has resided in Canada for nearly two years, you are probably best advised to apply in Canada in any case. A US consulate in Mexico would have more trouble verifying your information from the last two years, after all, than will one in Canada.
Here's what the US Department of State has to say about it, at Visas for Canadian and Mexican NAFTA Professional Workers:
You should schedule an appointment for your visa interview at the U.S. Embassy or Consulate in the country where you live. You may schedule your interview at another U.S. Embassy or Consulate, but be aware that it may be more difficult to qualify for a visa outside of the country where you live.
You live in Canada. You should apply in Canada.