Legal or illegal....the whole concept of "if we see someone carrying concealed we are going to ask to see their permit" (my paraphrase) is OXYMORONIC in its very foundation. The words chosen by the NFM spokesman display an ilLOGICal grasp of reality and poor choice of words. If ones sees a "concealed HG" LOGICally it is no longer concealed and in Nebraska and Kansas where they have stores is NOT against the law i.e. no state law forbidding OC (OC IS against the law in TX). That being said, really all they could do or have the right to do (and I support their right to such as a private business owner) is ask you to leave.
My finals thoughts....someone with a CHP should have some minimal intelligence to STAY CONCEALED. I would be reluctant as a hired security guard for NFM to approach someone who becomes "unconcealed". My intuition would lead me to become more suspicious of a BG or at least someone who may become beligerant when I request to see their CHP. All and all ....not a lot of LOGIC used in the company policy if written as the article indicates.