This is a nice application of $W=F\Delta x$ for mechanical work, or its rotational analogue $W=\tau\Delta\theta$. Molecules in a liquid are free to rotate, so $\Delta\theta$ can be large. If you think of the lattice in an ice crystal as being built out of individual water molecules, then $\Delta\theta$ is limited by the ability of the lattice to deform, and you get a much smaller amount of work done by the electric field.
If you try melting a stick of butter in the microwave, you'll see that it doesn't melt evenly. The melting starts in a certain spot, and then the spot spreads. The idea here is that once you get even a tiny bit of liquid, that liquid becomes efficient at absorbing energy, so the process snowballs. For this reason, I don't think you can test the theory by trying to use ice that has been thoroughly dried. As soon as the tiniest amount of liquid forms, it starts to grow.
Some possible experimental tests:
The explanation is independent of the detailed nature of the substance, so it should be true for all substances that the solid heats more slowly than the liquid. This seems to be verified by the fact that butter acts the same way as water.
An insulating liquid without any electric dipole moment should heat more slowly than one like water that has a dipole moment. I don't know of a safe, easy example, though.
[EDIT] Reading a little more on the web, it turns out that there are four qualitatively different effects by which microwaves can heat matter:
dielectric heating -- This is the effect I described above.
ionic conductivity
electronic conductivity
hysteresis
In most foods, 1 and 2 are of approximately equal strength. 3 can occur in soot particles formed when food burns. In pure water and ice, only 1 is significant.