I have (so far) pretty good experiences with the following brands:
Hahmel (sp?), for the PowerShot S40
GP, 511A replacement for the 20D
The former has proved to live longer than Canon's original batteries, and is in markedly better shape after two years than Canon's was after the same time.
The GP performs similarly to the original 511A as far as I can tell, but I've only taken about 3400 shots with my 20D, so I can't exactly claim to have stress-tested either the original or the GP.