Ok, I've done some more experimentation and found that fastmail does in fact reconcile, but only when I hit the "reconcile now" menu item. It may do it automatically when it polls for email, which takes a while because it sure isn't push!
Gmail definitely does not reconcile in any direction, in any way. I do get push, but nothing else.
I was going to try Yahoo, but I've read several places that Cingular doesn't support push on Yahoo mail...anyone have any experience?