Static position and orientation sensing

I've used the Allegro 3503 ratiometric linear sensor. It's discontinued, but I suspect its similar to the 1301/1302 sensors. It is very linear when positioned between two opposing magnets. This particular config (push-push mode) is shown on page 27 of the guide that you can download at http://www.allegromicro.com/en/Design-Center/Technical-Documents/Hall-Effect-Sensor-IC-Publications/Hall-Effect-IC-Application-Guide.aspx, but there are some other interesting modes. Give that ref a good read. You are talking mm here, and not cm. I think if you have a small 1 mm range, you can probably get 0.5 mm resolution, but I can't say I've pushed it that far. Strong neodymium magnets would certainly help.

They're even easier to use than you describe. The output voltage simply changes as a function of flux density.

As a design alternative, you might consider an optical position sensitive detector from Hamamatsu. You'd just need a 1-D sensor. They're good to about 50 microns over two millimeters.

According to your current specifications, a possible solution would be to use two small cameras and stereoscopic computer vision to locate the object.

It will require a line of sight to the object, knowledge of how the object looks like, an adequate resolution to the size and distance of the object, quite some processing (OpenCV may help) and accurate knowledge of the position of the detector.