Well, for the truly paranoid... you can always look into proxy chaining.

I have had mixed results with these. If you are on dial up, then you'll probably be ok, but on broadband... most of them are too slow. Especially if you are bouncing around the world.

Read about proxy chaining here or search google. There is a lot on them.

Oh, to answer your question. yes, most of the proxies out there do log everything. It has more to do with covering their a$$ when they are confronted by the authorities.
They don't want to be the blame for some script kiddie causing havoc on the net.

They are quick to dump their logs though, as long as they don't get any visits... so if you are looking to do something that is questionable by law... proxies aren't the way to go. If you are looking to do something questionable... you might want to stop and think again. Is it really worth it? I'm not accusing you of looking to get into trouble. I'm posting this more or less for anyone who stumbles on this thread thinking that they're l337 cause they "spoofed" their ip with a proxy and haven't yet been caught...

They help keep you "private" to web sites but don't keep you private from the law. What would u do? Take the fall for some skiddie, or turn them in? You know the answer...