Radio triangulation on millimeter scale plausible?
Using a different method than what you propose, achieving navigation by "bots" at the size you specify does meet your fair game" criteria - but it's almost certainly beyond what is reasonable now.

Note that the scale of your 'bot' is in the same order of size as a current IC transistor cell - so you are going to need some other technology changes along the way. 



I am in the process of trying to explain to people how you can telemeter the position and orientation in space of say a cylinder 2mm in diameter and say 4mm long. That's 2000 micron x 4000 micron, so "rather larger" than what you have in mind but small by most modern standards. The system used should scale to your bots level, provided that you can fabricate to dimensions substantially smaller again - say 100 Angstrom or less wires :-).

A method that does work is to use orthogonal coils (2 or 3) and linearly varying 3D external fields to allow the 'bots' to determine their position.  Fields are set up using various methods similar to those used for NMR (Helmhotz coils and other). This is not at all hard to do compared to the rest of the problem. 

Good results are currently reported using coils of under 2mm diameter and the principle can be extended downwards in size. Also, systems like GMR. AMR and other can be used for field angle measurement. It is possible to determine position and orientation from such a system.

I have obtained several papers which I can provide references to which show what has been done recently. I can provide references in due course if of interest - rushing off elsewhere at present. 

Note that powering is an issue at very small scales. Work out how much energy you can store electrochemically! Remote power transfer becomes attractive and is (probably) not too hard in comparison to all the other issues involved. 

Some people are using magnets and gradient field methods to actually navigate devices internally in people ! :-). 



One paper that I referred to is described below.
 Their sensor coils are 2mm diameter.
 They monitor the real time flight of a blow-fly with 1 kHz update or orientation and position in space. They are achieving 1mm positional accuracy, but that depends on aspects which will be makedly different in a much smaller system.

Their system has the massive advantage of having a "tether' - the wires are so light that the blowfly can free fly while trailing an "umbilical" cord. Your nanobots and my sensors do not have this luxury. 

J Neurosci Methods. 1998 Sep 1;83(2):125-31.
 Using miniature sensor coils for simultaneous measurement of orientation and position of small, fast-moving animals.
 Schilstra C, van Hateren JH. Department of Neurobiophysics, University of Groningen, The Netherlands.


Abstract  

A system is described that measures, with a sampling frequency of 1 kHz, the orientation and position of a blowfly (Calliphora vicina) flying in a volume of 0.4 x 0.4 x 0.4 m3. Orientation is measured with a typical accuracy of 0.5 degrees, and position with a typical accuracy of 1 mm.   

This is accomplished by producing a time-varying magnetic field with three orthogonal pairs of field coils, driven sinusoidally at frequencies of 50, 68, and 86 kHz, respectively. Each pair induces a voltage at the corresponding frequency in each of three miniature orthogonal sensor coils mounted on the animal.   

The sensor coils are connected via thin (12-microm) wires to a set of nine lock-in amplifiers, each locking to one of the three field frequencies. Two of the pairs of field coils produce approximately homogeneous magnetic fields, which are necessary for reconstructing the orientation of the animal. The third pair produces a gradient field, which is necessary for reconstructing the position of the animal.   

Both sensor coils and leads are light enough (0.8-1.6 mg for three sensor coils of 40-80 windings, and 6.7 mg/m for the leads, causing a maximal load of approximately 5.7 mg) not to hinder normal flight of the animal (typical weight 80 mg). In general, the system can be used for high-speed recordings of head, eye or limb movements, where a wire connection is possible, but the mechanical load on the moving parts needs to be very small.


The abstract is available at a number of places including here and here. Cost of viewing the paper is about $US30 if you do not have a relevant academic or other access. I can comment on the content but NOT send you a copy. Contact me privately if you wish. See my profile page for my email address.