Can pooling ever increase accuracy in convolutional neural networks?
I think this is a very interesting question. It tells me that you have a deep understanding of the basic concepts in machine learning, overfitting - underfitting, ... etc.

Let us start with making sure that we all agree that max pooling does not add any additional parameters to the network, max pooling is a well defined operation and there is no need to do any training to max pooling layers. 

The main challenge in answering your question is that it is really difficult to address the effect of having max pooling as part of the network without considering other factors: the curse of dimensionality (the size of the output of the feature extraction part), the size of the network (especially the fully connected layers) and the overfitting issue.

In one of the experiment I did, I tried to answer a similar question. But first, I want to isolate the effect of using max pooling from changing the size of the network. But how to do this: I replaced the max pooling function with a custom version: instead of pooling 1-value from (4 x 4), I used a custom function that pooling (4 x 4) from (4 x 4) where all the values in the output are equal the max value in the input (4 x 4). I increased also the size of the convolution kernels  in later layers (to make sure that I am looking at a larger receptive field in later layers)

You can see that there will be many redundant information. I was able to isolate the advantage of changing representation from sparse to rich representations. Which can be beneficial (think about max pooling in sparse coding to understand how this works).

The answer from my own perspective:


generating rich representations can improve the classification accuracy.
if you do not have max pooling, the fully connected layers can be really huge.
if you do not have enough data, you will have overfitting problem.
in my case, the database I have contains ~ 12M images, since data is the best regularization technique, it was difficult for me to understand if there is any overfitting problems (which I believe it will be the case if you do not have enough images).


I totally understand that from information theory point of view, we are loosing information in max pooling, but it looks like max pooling keeps the most important information that can be used to build a strong multi-layer full connected network at the end. 

please do not take my answer as an ultimate truth, I just wanted to share my concerns and thoughts about this based on one of the experiments I did before