I'd look at the Pentax Optio S4i. I think its everything you want, except full speed video (15fps). It's slightly more than you wanted to spend, but you might be able to find a previous 3.3MP version on ebay or something. The Optio is really tiny, about the size of an altoids tin. Weight is about 120g with battery and SD card loaded.

My GF got one of these and its really nice.

I believe that the Konica Minolta Xg has 30fps video out (don't know which resolutions), and the Sony DSC-T1 supposedly does 30fps at 640x480. I haven't played with either of those. They are both larger than the Optio.

Also, the Optio S40 (I think) is a version of the Optio that uses regular batteries. Its slightly larger, but doesn't rely on a proprietary battery.

FWIW,
Jim