Max-pooling vs. zero padding: Loosing spatial information
Pooling (max/mean/etc) has two primary benefits: it significantly reduces computational complexity (at the cost of potentially important data) and it helps the network achieve spatial invariance by making the spatial relativity between features less relevant.

However, the spatial invariance achieved through pooling is not always ideal.    For instance, given a CNN trained to identify images of automobiles, it would probably classify an image containing a hood/trunk, tires, windows, car doors, etc. as an automobile, regardless of the components' relative positioning.

On the other hand, I do not know of significant costs to using padding.  Zero padding is critical for deep networks; without it, our volumes would rapidly collapse through the layers.  It therefore helps to maintain desirable volume sizes and to preserve the border data.  It also helps the geometry of CNNs to work out smoothly by preventing mismatched dimensions between layers.

You might find this paper interesting.  Hinton and his team propose a new network called Capsule Network (CapsNet) that addresses the problems with pooling and provides an alternative solution for acquiring spatial invariance.  One of the many exciting parts of their algorithm is that the location of features relative to one another is a primary asset in the classification process, bringing computers closer to a "true understanding" of objectness.