They have quite a slow update rate, though. Some can be pushed into a higher speed, but that's possibly only the report rate not the measurement rate. It may be possible to move them fast enough that they lose position - they're not an absolute measurement (even when called that) but I'm unsure of the limits.
If they're fast enough, there are 150mm calipers often going cheap at Aldi etc. These use the same position encoders as the machine-mounted scales and may have the data port inside.
There's a company called US Digital which makes accurate magnetic scales as you describe yet still at prices below the precision glass scales (also available from the company Nigle linked). A Yahoo group called cad_cam_edm_dro is a good place to get advice about them.
I've also wondered about using optical (pattern sensing) mice to measure relative position. I'm not sure of linearity and it may be difficult to keep them sufficiently clean on a CNC machine, but they're very cheap and don't require a mechanical link to the surface.