Approaches to a few thousand individually addressable widely dispersed LEDs
This sounds like it might be a good application for a 1-Wire&reg; bus, using something like a DS2413 to control every LED or two, at least if those parts were a bit cheaper.  Otherwise, your best bet may be to attach each LED to a small microcontroller, and use a simple unidirectional communications scheme to send data to all the controllers.  Using a unidirectional scheme would facilitate the construction of very simple repeaters (simple non-inverting buffers would probably suffice).  Each microcontroller could use a small amount of flash or EEPROM to hold an address, so all devices could be individually addressed independently.  The biggest difficulty might be configuring the network; that might be best facilitated by having each controller include a command to output its address by modulating its light output.  An optical receiver attached to a portable computer could be used to visit each node, read its light pattern, and make note of its physical location.