The German government was hardly really negotiating a no-spy treaty. They benefit too much from the exchange with the US (at least that's what they think). Remember, the NSA is not supposed to spy on US citizens, just as the German BND is not supposed to spy on Germans. So they spy on each other's citizens and exchange the information.

So far so good for Merkel and friends. What probably upsetted them was that the German government was spied upon, too. Also, they were just second-grade allies, and the US was probably trading information with the UK for example, which they didn't share with the Germans (see the "Five Eyes" agreements). But it's hard to believe that any of this is news to the German government, if their intelligence agencies are any of their money worth.

So the big question is, why do they tolerate being spied on? I know, diplomacy is complicated, and you have to make a lot of delicate compromises, and there is a lot that you can't see from outside.

Nevertheless... Espionage is already punishable in Germany. If a German citizen is involved, they might even be charged with treason. If I were Merkel, I would just casually mention the possibility of pressing charges in this case (you can file charges against anonymous in Germany), and use this as leverage e.g. when negotiating trade agreements.