Fondueset,
I just completed a ton of home work on exactly what you're asking.. I posted questions on a local dive site and a site called
http://www.digideep.com and what came back was the canon A95.. which is the predecessor to what I bought, the Canon A610. I took about 100 pics, mostly flash, and about 5 minutes of video or more before I changed the batteries.. great. The A610 is actually less $$ then the A95 but has more features.. unlimited video, 3 qualities of video, good battery life, AA batteries, 5megpix, reasonable underwater housing.. I got new camera/1gig card/16meg card for $250u.s. at e-bay and an underwater housing good to 40mtrs for $165u.s. from an internet site.. that's a cheap setup for sure for all the stuff it does and the quality of photos I'm getting. I was glad for the advice I got. Good luck to you..
Fred