Virtual photon clouds are responsible for potentials, not electric and magnetic fields, and this is what makes the explanation of forces in terms of photon exchange somewhat difficult for a newcomer. The photon propagation is not gauge invariant, and the Feynman gauge is the usual one for getting the forces to come out from particle exchange. In another useful gauge, Dirac's, the photons are physical, and the electrostatic force is instantaneous.
When you have a solenoid, the photons are generated by the currents in the solenoid, and a charge moving through this virtual photon cloud has an altered energy and canonical momentum according to the distribution of the photons at any point in space. The effect can be understood from the current-current form of the interaction:
$$ J^\mu(x) J^\nu(y) G_{\mu\nu}(x-y)$$
Where G is the propagation function, and the current J is the probability amplitude for emitting/absorbing a photon. The propagation function reproduces the vector potential from a source J, as it acts on another source J at another point.
There is no difference between classical sources producing photons and classical currents producing a vector potential--- they are the same. The electric and magnetic field description is not fundamental, and the gauge dependence of the photon propagator is just something you have to live with.
If basic symmetry and homogeneity assumptions about the Universe hold, then yes, all massless real particles (see Anna V's answer for virtual particles must travel at a universal constant $c$, the speed of a massless particle, in all frames of reference.
Given these basic symmetry and homogeneity assumptions, one can derive the possible co-ordinate transformations for the relativity of inertial frames: see the section "From Group Postulates" on the Wikipedia Page "Lorentz Transformation". (Also see my summary here). Galilean relativity is consistent with these assumptions, but not uniquely so: the other possibility is that there is some speed $c$ characterizing relativity such that $c$ is the same when measured from all frames of reference. Time dilation, Lorentz-Fitzgerald contraction and the impossibility of accelerating a massive particle to $c$ are all simple consequences of these other possible relativities.
So now it becomes an experimental question as to which relativity holds: Galilean or Lorentz transformation? And the experiment is answered by testing how speeds transform between inertial frames. Otherwise put, the experimental question is are there any speeds that are the same for all inertial observers?. The question is not about measuring the values of any speed, but rather, how they transform. Now of course we know the answer: the Michelson Morley experiment found such a speed, the speed of light. So there are two conclusions here: (1) Relativity of inertial frames is Lorentzian, not Galilean (which can be thought of as a Lorentz transformation with infinite $c$) and (2) light is a massless particle, because light is observed to go at this speed that transforms in this special way.
Notice that at the outset of this argument we mention nothing about particles or any particular physical phenomenon (even though special relativity's historical roots were in light). It follows that, if $c$ is experimentally observed to be finite (i.e. Galilean relativity does not hold), then the specially invariant speed is unique: it can only be reached by massless particles and there can't be more than one such $c$ - the Lorentz laws are what they are and are the only ones consistent with our initial symmetry and homogeneity assumptions. So if we observed two different speeds transforming like $c$, this would falsify our basic symmetry and homogeneity assumptions about the World. No experiment gives us grounds for doing that.
This is why all massless particles have the same speed $c$.
Update: Experimental Results
As is now common knowledge, the gravitational wave event GW170817 and gamma ray burst GRB170817A give strong experimental evidence of the equality of the speeds of light and gravitation. As discussed in:
Gravitational Waves and Gamma-Rays from a Binary Neutron Star Merger: GW170817 and GRB 170817A
the 1.7 second time delay between the gravitational wave arrival and the gamma ray burst, together with conservative assumptions about other sources of delay, yields an experimental bound on the fractional difference between the speed of light and of gravitation:
$$\frac{v_g-v_{em}}{c} \leq 3\times 10^{-15}$$
an impressive experimental bound indeed. Within the next 10 years, we probably shall see several such events, and thus this experimental bound will tighten further (unless something really theoretically unforeseen happens!).
Mass From Confined Massless Particles
Incidentally, if we confine massless particles, e.g. put light into a perfectly reflecting box, the box's inertia increases by $E/c^2$, where $E$ is the energy content. This is the mechanism for most of your body's mass: massless gluons are confined and are accelerating backwards and forwards all the time, so they have inertia just as the confined light in a box did. Likewise, an electron can be thought of as comprising two massless particles, tethered together by a coupling term that is the mass of the electron. The Dirac and Maxwell equations can be written in the same form: the left and right hand circularly polarized components of light are uncoupled and therefore travel at $c$, but the massless left and right hand circular components of the electron are tethered together. This begets the phenomenon of the Zitterbewegung - whereby an electron can be construed as observable at any instant in time as traveling at $c$, but it swiftly oscillates back and forth between left and right hand states and is thus confined in one place. Therefore it takes on mass, just as the "tethered" light in the box does.
Best Answer
This is a good question. It's a well worn part of the trail when learning quantum field theory. A lot of folks come across this issue at some point -- at least, I know I did. Let's first reason physically then we'll do the math.
The most important thing you need to know about virtual "particles" is that they are not detectable -- at least not if you believe special relativity which says that a free particle of four-momentum $p^\mu = (E,\mathbf{p})$ and mass $m$ satisfies a constraint: $E^2 = |\mathbf{p}|^2 + m^2$ (or $p^2=p_\mu p^\mu = m^2$), which is just the mass-shell condition. And, as you've pointed out, a virtual particle is "off mass-shell." If you were to observe a particle that didn't satisfy the mass-shell condition, you'd violate special relativity. (I haven't explained where the mass-shell condition comes from but it's Lorentz invariance.)
"Real" photons are, by definition, on mass-shell. That is, for a photon of four-momentum $q^\mu$ we have $q^2=0$ ($m$ is zero). That is, if you measure the energy of a photon and the momentum of a photon you'll always find (in appropriate units) that they're exactly equal.
One more preliminary point: virtual photons appear in processes, described for example by Feynman diagrams, as intermediate state particles. This is just a restatement of the non-observability of virtual photons (or any virtual particle). While real photons can end up in a detector, like your eye -- they correspond to particle lines that leave a Feynman diagram.
Now, in answer to your question -- these photons are quite the same, if we ignore the off mass-shell/on mass-shell distinction. Or perhaps, ahem, they aren't quite the same, exactly. (Sorry to be coy here. The fact is the question can only really be answered in the context of a particular choice of gauge. An interpretation that depends on the choice of gauge isn't "physical" since the gauge dependence of observables must be trivial.)
Pressing on, the reason for this erstwhile difference is spin. The virtual photon can have three polarization states -- it's a genuine spin-1 particle. It can support a longitudinal polarization (unlike a real photon) since $q^2\ne 0$ and this means it has an "effective" mass. The real photon can only have two independent polarization states, parallel and anti-parallel to the direction of motion. This is a consequence of a property of massless fields of spin $\ge 1$ called gauge invariance.
Now for some of the mathematical statement of the above hand-waving argument. I'm going to assume that we don't need to go into detail about the description of the free, real photon field. (It's described well in any field theory book.) So we'll focus on the virtual photon description.
In field theory virtual particles are described universally by their propagators or two-point functions. Before explaining the origin of the propagator for massless particles (I can't reproduce the lengthy argument here but see Chs.(5.9) & (8.5) of Weinberg, QTF I for a detailed derivation), let's look at the propagator for the massive spin-1 field: \begin{align} \Delta_{\mu\nu}(q) &= \frac{-i}{(2\pi)^4}\frac{\eta_{\mu\nu}+q_\mu q_\nu/m^2}{q^2+m^2-i\epsilon}. \end{align} Clearly, something goes wrong when $m\to 0$ in the second term of the numerator. In quantum electrodynamics, however, the $\lim_{m\to 0} \Delta(q)$ is well defined since the photon couples only to conserved currents, $J^\mu=\overline{\psi}\gamma^\mu\psi$, $\partial_\mu J^\mu=0$. The upshot of this is that the photon (massless vector field) propagator is: \begin{align} \Delta_{\mu\nu}(q) &= \frac{-i}{(2\pi)^4}\frac{\eta_{\mu\nu}}{q^2-i\epsilon}. \end{align}
Now here's the interesting part. If you sum over all three virtual photon polarizations in calculating the propagator you get the above relation. But in order to be consistent, you'll ignore the Coulomb interaction. If one includes the Coulomb interaction, however, you'll sum over the two physical photon spin (helicity) states in the calculation of the propagator. The answer in either picture, of course, is the same. But the spin of the virtual photon is different in these two pictures, which correspond to the Coulomb gauge (where one includes the Coulomb interaction) or the Feynman gauge (where one doesn't).