Rechargable batteries have different ways of signalling to the charging circuitry that they're full, depending on the technology involved. This ranges from sinking a certain current to reaching a certain temperature. Ignoring these signs when charging a battery can result in the battery going boom (search some of the video sharing sites for what this looks like). Because of this, electronics manufacturers tend to err on the side of caution when they set up their charge circuits.
As batteries age, they lose the capacity to take a charge. This manifests as the "I'm full" signal coming earlier, which in turn results in less charge being stored in the battery. Thus the charging system says the battery is full (or rather, it can't be charged any more), while the level measurement (which shows charge remaining) says it's only half full.
How long have you had your rechargables, are they lithium ion or lithium polymer (not that this makes much difference), and how many charge/discharge cycles have they seen? Standard Li-Ions will be ok for around 1000 cycles (depending on use and charge speed), although they really don't like being left sitting for long periods with no charge. Li-Polys are a bit more forgiving, and the newer Li-FeO cells should be good for around 4000-5000 cycles (but I doubt there are any GPS units using these as yet).
In short, if your rechargable batteries are a bit old, and aren't holding charge like they used to, they probably need replacing.