We study the most general solution for affine connections that are compatible with the variational principle in the Palatini formalism for the Einstein-Hilbert action (with possible minimally coupled matter terms). We find that there is a family of solutions generalising the Levi-Civita connection, characterised by an arbitrary, non-dynamical vector field ${cal A}_mu$. We discuss the mathematical properties and the physical implications of this family and argue that, although there is a clear mathematical difference between these new Palatini connections and the Levi-Civita one, both unparametrised geodesics and the Einstein equation are shared by all of them. Moreover, the Palatini connections are characterised precisely by these two properties, as well as by other properties of its parallel transport. Based on this, we conclude that physical effects associated to the choice of one or the other will not be distinguishable, at least not at the level of solutions or test particle dynamics. We propose a geometrical interpretation for the existence and unobservability of the new solutions.