In my opinion this is an excellent question, which manages to puzzle also some accomplished physicists. So I do not hesitate to provide another, a bit more detailed, answer, even though several good answers exist already.
I think that at least part of this question is based upon an incomplete understanding on what it means to mediate a static force from a particle physics point of view. As others have mentioned in their answers already, you encounter a similar issue in the Coulomb problem in electrodynamics.
Let me answer your question from a field theory point of view, since I believe this concurs best with your intuition about particles being exchanged (as apparent from the way you phrased the question).
First, no gravitational waves can escape from inside the black hole, as you hinted already in your question.
Second, no gravitational waves have to escape from inside the black hole (or from the horizon) in order to mediate a static gravitational force.
Gravity waves do not mediate the static gravitational force, but only quadrupole or higher moments.
If you want to think about forces in terms of particles being exchanged you can view the static gravitational force (the monopole moment, if you wish) as being mediated by "Coulomb-gravitons" (see below for the analogy with electrodynamics). Coulomb-gravitons are gauge degrees of freedom (so one may hesitate to call them "particles"), and thus no information is mediated by their "escape" from the black hole.
This is quite analog to what happens in electrodynamics: photon exchange is responsible for the electromagnetic force, but photon waves are not responsible for the Coulomb force.
Photon waves do not mediate the static electromagnetic force, but only dipole or higher moments.
You can view the static electromagnetic force (the monopole moment, if you wish) as being mediated by Coulomb-photons. Coulomb-photons are gauge degrees of freedom (so one may hesitate to call them "particles"), and thus no information is mediated by their "instantaneous" transmission.
Actually, this is precisely how you deal with the Coulomb force in the QFT context. In so-called Bethe-Salpeter perturbation theory you sum all ladder graphs with Coulomb-photon exchanges and obtain in this way the 1/r potential to leading order and various quantum corrections (Lamb shift etc.) to sub-leading order in the electromagnetic fine structure constant.
In summary, it is possible to think about the Schwarzschild and Coulomb force in terms of some (virtual) particles (Coulomb-gravitons or -photons) being exchanged, but as these "particles" are actually gauge degrees of freedom no conflict arises with their "escape" from the black hole or their instantaneous transmission in electrodynamics.
An elegant (but perhaps less intuitive) way to arrive at the same answer is to observe that (given some conditions) the ADM mass - for stationary black hole space-times this is what you would call the "black hole mass" - is conserved. Thus, this information is provided by boundary conditions "from the very beginning", i.e., even before a black hole is formed. Therefore, this information never has to "escape" from the black hole.
On a side-note, in one of his lectures Roberto Emparan posed your question (phrased a bit differently) as an exercise for his students, and we discussed it for at least an hour before everyone was satisfied with the answer - or gave up ;-)