This thread actually is still relevant to me.
We ended up waterproofing the camera in the first image and it worked, but it's limitations were . . . very limiting . . .
I've done a new search in 2008, 2009, 2010, and most recently this year. In 2010 I had put in orders for a 'waterproof' spy cam and one of those rugged waterproof sport cameras to try out, but long story short government 'efficiency' resulted in nothing actually being ordered.
So yea, if you find anything, let me know!
ps - We are likely going to have double the payload space in our next robot fish platform, so probably can have double the camera size. I've seen plenty more cameras that can fit with that reduced restriction, but we'll see next year how things go before I look into the latest new camera technologies.