Do BTC payments have to be signed with the same keys used to get the BTC?
I do not believe that this is a problem. When some receives coins, they have no way of telling who it came from. So if the hypothetical exchanger* and the seller shared usage data, all they would know is that you (and many other people) bought coins, and that someone sent coins to the seller.
Of course, this is my understanding, and I’m not an expert.
*There’s no need to single out NLS.
I think you have mistaken “public key” cryptography for normal cryptography. Please read this (http://en.wikipedia.org/wiki/Public-key_cryptography), if that concept is new to you - Bitcoin uses this technology for coin transfers. Otherwise, I must misunderstand you.