BTCの支払いは、そのBTCを受け取ったときと同じ鍵で署名しなければならないのか?
これは問題にならないと思う。誰かがコインを受け取っても、それが誰から来たのかを知る方法はない。だから、仮にその両替商*と売り手が利用の記録を突き合わせたとしても、分かるのは、あなた(とほかの大勢の人)がコインを買ったことと、誰かが売り手にコインを送ったことだけだ。
もちろん、これは私の理解であって、私は専門家ではない。
*NLSを名指しする必要はない。
あなたは「公開鍵」暗号を、普通の暗号と取り違えているのだと思う。この考え方になじみがなければ、これ (http://en.wikipedia.org/wiki/Public-key_cryptography)を読んでほしい。Bitcoinは、コインの受け渡しにこの技術を使っている。そうでないなら、私があなたの言うことを誤解しているに違いない。