We investigate the geometrical frustration in two-dimensional lattice-based mechanical metamaterials comprised of anisotropic hexagonal building blocks $H$, where each $H$ possesses a nontrivial floppy mode of deformation. When each hexagon is oriented randomly, neighboring hexagons typically cannot deform self-consistently. Using combinatorial approaches we demonstrate that the number of frustration-free large-scale structures (i.e., structures that exhibit a global floppy mode compatible with the local floppy mode of each hexagon) scales sub-extensively in the number of hexagonal unit cells $N_H$, suggesting a long-ranged holographic order: $\Omega_0\sim\exp{\lambda\sqrt{N_H}}$, with $\ln{2}<\lambda<2\ln{3}$ for a rhombic lattice. We further investigate the mechanical consequences of frustration by performing numerical calculations in the linear elastic regime, and compare our results to an experimental porous metamaterial.