I replaced two batteries now, bought them on Ebay, put them in myself. Spent 450 and 600, so definately don't go to the dealer. I have 2001 and 2002 models.
GEN II here - I just had my 2005 with 109k hybrid battery die on 2-17-12, getting P0a80 and P3012 error code, running limp mode, it was used allot in cold weather and short distance driving in NYC, maybe that accelerated deterioration. I'm getting it shipped to reinvolt hopefully this week. I really like the car but its really got me questioning the environmental \ savings if these battery replacement prices don't go down.