> And why didn't that logic work for US State Dept phones?
These were Foreign Service officers stationed in Uganda, so their phones had local Ugandan phone numbers. Some of them were working out of DC but - given the nature of the State Department (which is like America's foreign affairs department) - probably traveled very frequently and so maintained a Ugandan phone number as well, to save on roaming fees when making calls in Uganda (saving money for the taxpayer) and also so Ugandan officials can contact them easily.
This is not unlike Apple hardware engineers who travel frequently to China and have a Chinese number in addition to their main US number, so people in the factory can communicate with them easily.
> So I just have to buy a US phone [number] to evade detection from NSO?
This is NSO's claim. Presumably because they want to make it difficult for anyone to sue them in a US court. It's plausible but I don't necessarily believe them either.
I want this company bankrupted out of existence, personally. Apple's lawsuit against them may well result in that outcome.