Particles for all forces: how do they know where to go, and what to avoid? Here's an intuitive problem which I can't get around, can someone please explain it?
Consider a proton P and an electron E moving through the electromagnetic field (or other particles for other forces, same argument). They exert a force upon one another. In classical mechanics this is expressed as their contributing to the field and the field exerts a force back upon them in turn. In quantum mechanics the model is the exchange of a particle.
Let's say one such particle X is emitted from P and heads towards E. In the basic scenario, E absorbs it and changes its momentum accordingly. Fine.
How does X know where E is going to be by the time it arrives? What's to stop E dodging it, or having some other particle intercept X en route?
Are P and E emitting a constant stream of force-carrying particles towards every other non-force-carrying particle in the universe? Doesn't this imply a vast amount of radiation all over the place?
I am tempted to shrug of the entire particle exchange as a mere numerical convenience; a discretization of the Maxwell equations perhaps. I am reluctant to say "virtual particle" because I suspect that term means something different to what I think it means.
Or is it a kind of observer effect: E "observes" X in the act of absorbing it, all non-intercepting paths have zero probability when the waveform collapses?
Or have I missed the point entirely?
 A: In a non relativistic Classical Mechanics (CM) there is an interaction potential involving both coordinates: $U(\vec{r}_1-\vec{r}_2)$ and the corresponding force present in either particle equation. There is no need in "exchange" interpretation here. Same for non relativistic QM.
In relativistic case the potential becomes "retarded". Its time evolution may be expanded in a Fourier series and each plane wave can be called a "longitudinal virtual photon". You see, it it nearly the same interaction potential (force) as in the non relativistic CM, acting between charged particles. 
Apart from retarded "longitudinal" potential, there is also "transversal" vector potential that may include real electromagnetic waves propagating in all directions, not only between charged particles in question. The real photons are not absorbed but scattered so they do not contribute into the charge "attraction". The latter is described with those "virtual photons".
A: As Jerry Schirmer points out, it is not really a  discretization of the Maxwell equations as you say, but rather a series expansion of the quantum mechanical cross section for interaction. Thus you put in an electron and a proton with some momenta and you want to calculate the probability of them coming out with some other momenta, which you can express as something like
$${}_\textrm{out}\langle p^+,q_1;e^-,q_2|p^+,p_1;e^-,p_2\rangle_\textrm{in}=\lim_{T\rightarrow\infty}\langle p^+,q_1;e^-,q_2|e^{iH(2T)}|p^+,p_1;e^-,p_2\rangle.$$
You then make a series expansion of this quantity in the interaction hamiltonian (or more exactly in the interaction strength $\alpha=e^2/\hbar c$). Feynman's contribution (one of them, anyway) was to give a graphical way of constructing each of the terms in the series (most of which involve pretty ugly integrals and will in fact diverge if not treated properly using renormalization) so that each term gets interpreted as a physical process where, say, the electron and proton interchange a virtual photon.
The truth is of course that these virtual photon exchanges are not physical: only the whole scattering process is physical and you cannot observe what happens in the middle.
A: This choice is closest to the  the correct one.

I am tempted to shrug of the entire particle exchange as a mere numerical convenience; a discretization of the Maxwell equations perhaps. I am reluctant to say "virtual particle" because I suspect that term means something different to what I think it means.

And virtual exchange is a correct description, because during the interaction the exchanged particle is not on mass shell.
Keep in mind that in the  microcosm of particles nature is  quantum mechanical. The particle scattering on another particle and the momentum and energy and quantum number exchanges between them are all described by one wave function, one mathematical formula that gives the probability for the interaction to take place in the way it has been ( will be )  observed.. Thus it is not a matter for "knowing" but a matter of "being".
The Feynman diagrams that give rise to the "particle exchange" framework are just a mathematical algorithm for the calculations and help in understanding how to proceed with them.
To see how classical fields are  built up by the substructure of quantum mechanics see the essay here. 
A: In the particle exchange picture, the particles are emitted in all directions and only the ones going from P in the direction of E that hit E are intercepted and have an effect. The other particles interfere themselves out of existence, as there is no on-shell state they can enter while conserving energy, or else return to P, giving the self-energy modification to P's mass. In fact, most return to P, since the self-energy is divergent, while only a small fraction make it to E by comparison.
This process is virtual, so that it is defined by temporary intermediate states which only can stick around until their phase randomizes them away. For the case of a classical force, you need to use particles that go every which way, forward and backward in time.
Consider two classical objects interacting with a (free) quantum field according to this Lagrangian:
$$\int |\partial_\phi|^2 + \phi(x) s(x) $$
where the source is two delta functions $s(x) = g\delta(x-x_0) + g\delta(x-x_1)$. Each of these classical sources is steadily spitting out and absorbing particles per unit time at a steady rate g, as you can see by the added source term in the Hamitlonian:
$$ g\phi(x_0) = g\int {d^3k\over 2E_k} e^{ikx_0} \alpha_k + e^{-ikx_0}\alpha^\dagger_k $$
the g term is multiplying a creation operator and an annihilation operator, so the Hamiltonian has a steady amplitude g per unit time to emit any on-shell particle, and the same amplitude to absorb one. If you have no other source, the particles that are absorbed are those emitted by the source, and you just get an (infinite) self-energy renormalization of the mass.
This description is the on-shell old-fasioned perturbation theory, in which the intermediate states are k-states and the description is Hamiltonian in time. This is not covariant, but it shows you that particles are spat out and absorbed, and the two sources only interact to the extent that some of the particles spat out by one are absorbed by the other. The old-fasioned picture is useless for actual computations, but it reveals the particle processes most clearly, because it follows the annihilation and creation of physical particles in detail in time.
The result of the interaction when there are two sources is altered by those particles produced by one, absorbed by the other later. The covariant Schwinger/Feynman form of this introduces particles that meander around in space and time both. Those that do not get absorbed by the other make a field around the particle.
The fact that you are doing things by loop order means that you are not considering the process of a particle emitted by one source absorbed by itself, since this is a loop. The loop order separation of terms makes the scattering process look weird, since it looks like the emitted particle knew where to go to find the other particle. It didn't. If it came back to the first particle, we would include it as part of the next order of Feynman diagram as part of the self-energy graph.
A: The following is very loose and sloppy; I wanted to try explaining it on a pop level.
Remember that reality is not what our intuition suggests it is. A "particle" is not just a particle: it is also a wave; it is also an excitation of a field. It makes sense in some situations to predict results by thinking of "particles" as having a specific position and momentum, but that's not their essential nature (and is actually in conflict with reality as verified by numerous experiments).
In your example, when the proton P emits a photon X, you really ought to think of it as emitting a light wave which doesn't have a nailed-down orientation. Rather, it has a probability (calculable, with difficulty) of being at any number of different points, until it "interacts" with the electron and the "wavefunction collapses". I'm putting these events in quotation marks to emphasize that there are different possible interpretations, but they do accurately describe the underlying reality.
To address your specific questions, I'm going to be a bit sloppy.


*

*How does X know where E is going to be by the time it arrives? What's to stop E dodging it, or having some other particle intercept X en route?


P doesn't "know" where E is going to be and neither does X, but they don't need to. X doesn't start out as a particle, it starts out as a spherical wavefront, and whenever the X wavefront impacts E, suddenly the whole X-wave "pops" into an X-particle just at the right time and location to interact with E. E can't dodge the wavefront unless it's going faster than light. It's certainly possible for some other particle (F) to get hit by the X-wavefront and interact with it instead, but that means F is going to be sending out wavefronts too and we have a three-particle interaction instead of a two-particle one, and remember P is continually sending out wavefronts and some of them are going to hit X. (It's perfectly possible for one particle to shield another from the action of a third; that's how a Faraday cage works)


*

*Are P and E emitting a constant stream of force-carrying particles towards every other non-force-carrying particle in the universe? Doesn't this imply a vast amount of radiation all over the place?


You could think of it like that, but it's not like P and E know the positions of all other particles; they just send out their fields/wavefronts "everywhere" and it just so happens that the right amount of energy appears at the right place and the right time to make everything work. At placetimes where there's no particle to interact with, well, if a tree falls in the forest and so forth, it doesn't matter.
If you really want to blow your mind, consider that the equations about photon emission also admit a solution where the photon moves backwards in time. So, if you naively interpret that literally, anyone time-travelling to the past would be blinded because all the photons from all times in the future would be constantly bombarding them.
