If it makes you feel any better, out here in the sticks we lose power on a weekly basis throughout the winter and at least monthly in the summer. Because we have such a low population density, we're at the bottom of the 'to be fixed' list -- after all the area dairy farms are back on line, they'll get to us.

The wet sheet trick absolutely works, and we've discovered that you can get great battery powered fans at the dollar store. Often these are labeled with the logos of particularly unsucessful sports teams, but I imagine that you could paint them if that bothered you.

Also, real goods has some great solar powered fans, although they are far more pricey (and not much use at night unless you've charged them ahead of time)