Wow, I ended up doing something really convoluted the last time I ran into this issue by making all the objects immovable until collided with, yielding mixed results.
I thought the pixel rounding was purely a visual thing.
I always wonder how games like Angry Birds solve it, whether they use a totally different engine, or a heavily modded version of Box2d when it comes to their rather complex layouts.