Can virtual particles, in particular gravitons, interfere? Question 1. Can virtual particles, in particular gravitons, interfere?
Virtual particles are created and annihilated in a distance too small and a time too short to be measured. Their existence is allowed by Heisenberg's uncertainty principle, which allows a transitory violation of energy conservation in processes that endure a short enough time.
The electromagnetic interaction has a single force carrier, the photon. The weak interaction has two force carriers, the W and Z particles (with 2 signs for W). The strong interaction has 8 force carriers, the gluons. 
The quantum carrier of the gravitational force is the graviton (a massless spin 2 particle). Gravitons act together in such vast numbers that there is a scant hope to seeing evidence for just one or a few. 
I think that it is established that the less energetic the force carrier, the stronger is the force mediated. If gravitons can interfere, then it is likely that they would interfere destructively (chance dictates that both constructive and destructive interference are present, but destructive interference is more likely, that we can prove). From Planck's relation from quantum mechanics, that means that these gravitons will be less energetic, thus increasing the strength of the force of gravitation, over large scales. 
I emphasize that the probability of graviton interference increases for large scale systems (galaxies, clusters of galaxies), and it is very small for small scales, due to the ephemeral character of the virtual particles, in this case the graviton.
Here is my second question.
Question 2. Could this lead to a solution of the dark matter problem (a more accurate analysis than sketched here, of course)? Is it possible that the accumulated tiny effects of graviton interference in the Planck region could lead to an observable deviation from the known laws of gravity at very large scales (galaxies, clusters of galaxies), thus solving the dark matter problem?
 A: You first ask whether there could be interference effects between virtual gravitons. Assuming something like the standard theory for particle interactions (quantum field theory) would apply to a quantum theory of gravitons, there would indeed be interference between virtual gravitons. 
The total probability of a scattering event involving gravitons, say $ee\to ee$ with intermediate gravitons, would be a sum of all possible intermediate states involving gravitons. There would be interference between these intermediate states.
It's unlikely, however, that the effects of quantum gravity could solve the dark matter problem (your second question). The effects of quantum gravity are thought to be important only for incredibly large energies (energies similar to the Planck mass). Large energies are equivalent to very small distances (because of the de Broglie wavelength).
The evidence for dark matter is from experiments testing a few different distance scales, but all of them are much much bigger than the small scale (the Planck length) at which quantum gravity should be relevant.
A minority of physicists think the dark matter problem could be solved by modifying gravity (e.g. Modified Newtonian Dynamics), but their theories don't involve quantum gravity, just modified but classical gravity. 
A: 
Question 1. Can virtual particles, in particular gravitons, interfere?

Gravitons are the hypothetical carriers of gravity, corresponding to the photon for electromagnetism, with a very weak coupling to matter in comparison to all other forces:
With the strong force coupling at 1, the electromagnetic is at 1/137 , the weak 10^-6, the gravitational 10^-39.
Supposing for a valid quantization of gravity, the graviton graviton interaction will go through loops of other matter particles, making the interaction between two gravitons practically infinitesimal, 10^-78 . 
So the graviton-graviton interaction will be very small.

Question 1. Can virtual particles, in particular gravitons, interfere?

Gravitons, if they exist, are like photons, not like virtual particles.
Interference in quantum mechanical terms comes from the superposition of the individual wavefunctions to an over all wavefunction of two gravitons,  Psi. The superposition is linear and the  probability density of the superposed Psi*Psi has the interference effects, without interaction. Just from the nature of the probability density.
Virtual particles are not in that ball game, they are within an integral and interference or interaction has no meaning . They are part of the mathematics keeping track of quantum numbers and energy momentum conservation.
The answer is that virtual particles do not interfere. Gravitons are real particles like photons and can interfere if in the same spacetime region

Question 2. Could this lead to a solution of the dark matter problem

The answer is no. Graviton graviton interactions are much  worse than photon photon interactions, and interference effects are irrelevant in accumulation of bulk mass.
You might be interested in reading the wiki entry on the graviton.
A: The question on whether virtual particles (gravitons) can interfere is preceded by some arguments that contain a number of statements in need of careful consideration. So before I address the question, I'll first look at these statements:
1) 

"Their existence [virtual particles] is allowed by Heisenberg's
  uncertainty principle, which allows a transitory violation of energy
  conservation in processes that endure a short enough time."

This statement reveals a common misconception about Heisenberg's uncertainty principle. It actually specifies a minimum uncertainty and not a maximum uncertainty. In other words, to satisfy the Heisenberg uncertainty principle, something needs to exist a long enough time and not a short enough time. Something cannot `hide underneath' the uncertainty. No, the principle states that it is fundamentally impossible for anything (even virtual particles) to exist for shorter than a certain time given by the energy uncertainty.
2) 

"...it is established that the less energetic the force carrier, the
  stronger is the force mediated."

Actually this is only true for non-Abelian theories (such as QCD and electroweak), as far as I know. Their couplings become weaker for higher energies. Other theories, such as QED grow stranger at higher energies. A quick survey of literature seems to indicate that there is a disagreement on whether quantum gravity can be said to have a running coupling.
3) 

If gravitons can interfere, then it is likely that they would
  interfere destructively (chance dictates that both constructive and
  destructive interference are present, but destructive interference is
  more likely, that we can prove)

I would like to see that proof. Perhaps you can give a reference. Heuristically one can argue that destructive and constructive interference should be equally likely. The reason is that there must be energy conservation. In a random light field for instance one would find speckle, which contain bright spots and dark spots, such that the average intensity would maintain energy conservation.
4)

From Planck's relation from quantum mechanics, that means that these
  gravitons will be less energetic, thus increasing the strength of the
  force of gravitation, over large scales.

Based on the concerns mentioned above, this conclusion is questionable. In fact it is basically ruled out by observations. A force that grows stronger with distance would arguably reach a distance beyond which it become non-perturbative. It other words, it would confine itself just like QCD does. We see absolutely no evidence for that.
Question 1:
So let's consider the question about whether virtual particles can interfere. (In the context in which this question is being asked, I seriously doubt that this answer, or any of the other answers, would address the actually issue that the OP wishes to raise. There are simply too many misconceptions. However, for the sake of the question itself, and because the current two answers disagree with each other, I'll throw in my attempt.)
Virtual fields are perhaps most rigorously found as being represented by the internal lines in Feynman. The reason for them being virtual is because they are off-shell - i.e. they do not satisfy any dispersion relations. From this understanding it then followed that some physicists suggested that the force fields around particles (such as the Coulomb field around a charged particle) can be viewed as a virtual field. 
When we want to say whether these virtual fields can interfere, we need to agree about what we mean by interference. It most situations this is understood to be found when different fields can form a linear superposition. Under certain situations this superposition may be observed as interference fringes. However, fringes do not need to be present to represent an interference phenomenon. There is for instance also the case of quantum interference in, for instance the Hong-Ou-Mandel effect.
So if we restrict ourselves to the case of virtual fields as they appear in Feynman diagram. Then indeed we have a linear superposition of infinitely many different contractions of the different fields (plane waves, both on and off shell). This linear superposition exists in the form of integrals over all the phase space degree of freedom that are involved in the diagram. Well that would mean that we have the scenario of interference, and since in incorporates virtual field, it then follows that such virtual fields also interfere.
Sadly, such an interference cannot be observed in the same way that one would observe interference in a classical optical field. The effect of the interference is more a sum-over-histories kind of interference that determined the probability amplitude for a specific interaction.
Question 2:
In view of the above, it is strongly doubtful that this could explain dark matter.
A: As i see it a gravitons would interfere if gravity waves interfere. And I certainly think that a gravity wave would interfere. I guess that they are transverse waves that can interfere like any other waves.  
