Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes 
throughout the world which permit him to observe all exchanged data and all
computations done inside the nodes.

Is it still possible under these conditions to ensure by mathematical means
that this secret service cannot find out who communicates with whom,
if one designs internet protocols in a suitable way?

My feeling is that the answer is likely "yes", but I am not working in cryptography.
-- Probably a cryptographer can tell more. 

<b> Clarification (added after the first two answers): </b>
A good answer to this question could either consist of a description of
a method together with substantial heuristic arguments in support of its
suitability for the given purpose, or it could give substantial heuristic
arguments that there is no such method. Mere handwaving arguments in
favor of a positive or a negative answer do not answer the question.

On the other hand, the question is only meant to ask whether there are
mathematical methods which *in practice* serve the purpose,
just like *in practice* RSA can be used as a public key cryptosystem.
It is not asking for a proof or disproof (of what precisely??), since this
would not make sense.

<b> Added after the first 5 answers (excluding deleted one(s)): </b>
The answers given so far mostly take the question as a soft question,
which it is not. So far, Goldstern's answer comes closest to answering
the question in that it proposes a concrete method -- but as it stands,
it is still quite a way to go to get to anything practical.

Let me also emphasize that *any* transmission of data is "communication",
including transmissions of publicly available webpages, downloads etc..
So firstly everybody has *a lot* of communication partners, and
secondly efficiency is a very important concern.