Virtual photons as force mediators in QED - really? If the photon is the force vector for EM interactions, e.g. electrons, how does each electron 'know' where the other one is so that it can send it a photon?  I've thought about this for a while. I know one could easily say "that's why they're virtual", but really this just says to me - "it's magic, and we don't really know, but it helps us to figure things out, and we haven't a clue how things REALLY work".
 A: These are just my thoughts as someone who studied the subject for a while:
The concept of virtual photons that mediate interaction should not be seen as "what really happens". A virtual photon is not a real object (hence the name "virtual"), but an artifact of perturbation theory. If we knew an effective way (or even "a" way) to do the calculations without perturbation theory, all we'd need is quantized fields. At no place would we see the need to introduce force mediation by virtual particles. So "what really happens" might just be a particle seeing the field created by another.
Now a field "makes sense", i.e. we are accustomed to them from classical theories and your question can be easily answered in this setting: The electron doesn't know where the other particle is, it just creates a field everywhere and the other particle reacts to it. 
It also sort of "makes sense" that the field should be quantized, i.e. excitations (like waves) have discrete values in energy, etc. We know this from ordinary quantum mechanics. This is all there is - this is what you can measure (and in this sense, this is "what is real"). 
However, we don't have a way to do QED (or QCD) without using perturbation theory and when we do perturbation theory, we obtain the virtual photons. So in a sense, we do have an intuition what really happens (field theory + quantum mechanics), but that doesn't help us in doing calculations. To do this, we need perturbation theory and in order to "understand" the results of perturbation theory, it is nice to think about the virtual particles as actual particles mediating the force, just in the way anna v says. 
A: 
If the photon is the force vector for EM interactions, e.g. electrons, how does each electron 'know' where the other one is so that it can send it a photon? 

Virtual particles are in the realm of quantum mechanics, which is the framework necessary to describe the behavior of the micro world, with dimensions compatible with hbar. They have been postulated ever since Feynman diagrams became the tool for calculating interactions at the elementary particle level, and are the internal lines in these diagrams. They carry the quantum numbers of the named particles but not the mass, which can be off mass shell.
In the classical framework the electron has an electric field that extends to infinity and your question does not arise. The field of other electrons interfere with its field and the interference is how an electron "knows", of the existence of the others.
Physics though is continuous. The classical framework emerges from the quantum mechanical smoothly.  In the quantum mechanical framework the existence of another electron in the universe of the first electron generates a  probability of interaction between them with the exchange of a virtual photon, calculable by a simple Feynman diagram. 

The probability is very very low if the distances and momenta are not within range of hbar values. 

I've thought about this for a while. I know one could easily say "that's why they're virtual", 

It is called a virtual photon because it carries the quantum numbers of the photon though its mass in the diagram can be different from zero. 

but really this just says to me - "it's magic, and we don't really know, but it helps us to figure things out, and we haven't a clue how things REALLY work".

Define magic, and define REAL.
Physics is the way to organize observations in mathematical models so that magic can be reduced to a few postulates and mathematical models. The magic of previous centuries is the physics of this one.
The Feynman diagrams work in calculating very complex interactions of elementary particles very accurately. That is REAL for a physicist.  Calling the mediating lines in the diagrams by the on mass shell name of the particles helps in keeping track of the quantum numbers in the diagrams written down and then calculated. That is all.
At the microcosm the only tools we have are macroscopic measurements of what we calculate, when these work we define the models as really describing the microcosm. For everyday life classical fields are more than enough to describe real observations.
