It's because MSN Messenger 7.0 and newer versions resize the Display Picture again when it is shown on your contact's side.
Edit: Right, I misread a bit of your post.
As lordy16 said, both you and your contact need StuffPlug so that they can see your Over Sized DPs, and you can see theirs.