Update on this topic. We got it fixed. My wife called NHI the next day and got someone more competent on the phone. NHI sent a formal request to NIA to pull my immigration records, and with that NIH started billing me again. NHI had indicated that they would bill me only after verifying my eligibility.
So if you get an incompetent group of clerks like we did, don’t give up! The law is clear on this.