The bot does have a basic location detection scheme. When it gets out of range of the IR tower, it spins until it is facing it again and then heads that way. It's not very accurate, but at least you know that the bot is somewhere in the range of the IR tower (which, if you know the location of the IR tower, gives commercial grade GPS resolution).
In order to get a more accurate picture of the explored environment, some type of location detector would be an improvement. Obviously, military grade GPS isn't in the budget. Perhaps something could be done with a light source (such as IR) to provide a way for a robot to triangulate its location within a fixed space. However, this would probably require more math than the RCX is capable on its own (though the PC should be able to help). I haven't really investigated the best approach to this given a Mindstorms kit.