Rechargeable batteries are great, but they don't last very long, even when not in use. I've noticed the rechargeable batteries in one camera that I don't use very much tend to need recharging almost as often as the ones in the camera I use every day. NiMh are an improvement over the original NiCads (I couldn't even find any of those to test), but they still go flat even whilst sitting on the shelf. They are great for high drain applications like cameras or games where they are likely to be drained before they self discharge.
BatteryLogic.co.uk - I'm happy to recommend specialist sellers like these as I have been very impressed by their service (even around Christmas time), and I'm getting sick of poor service from big players like Amazon and eBuyer.