Why don't we decorrelate transitions for policy-based data?
We do decorrelate training experience, even for policy gradient methods. This is because decorrelation helps training data be more like IID data, which helps with the convergence of SGD-like optimizers. 

The shuffling is done on line 151 of OpenAI's "baselines" implementation of PPO.

I'm going to guess that there's a bug somewhere in your implementation. If you're using the same truncated advantage estimation as in the PPO paper, 

$$\begin{align}
&amp;\hat{A}_t = \delta_t + (\gamma\lambda)\delta_{t+1}+\dots+(\gamma\lambda)^{T-t+1}\delta_{T-1}\\
&amp;\text{where}\quad\delta_t=r_t+\gamma V(s_{t+1})-V(s_t)
\end{align}$$

make sure you're not shuffling experience before computing your advantage estimates $\hat{A}_1,\dots,\hat{A}_T$. Each of these estimates is a function of several unbroken steps of experience. After you compute your advantage estimates, then create the tuples $(s_t, a_t, \hat{A}_t)$ and shuffle and sample from those. I think that's all the information you need  per time step for constructing their objective function.