We study random walks on $\mathbb Z^d$ among random conductances $\{C_{xy}\colon x,y\in\mathbb Z^d\}$ that permit jumps of arbitrary length. Apart from joint ergodicity with respect to spatial shifts, we assume only that the nearest-neighbor conductances are uniformly positive and that $\sum_{x\in\mathbb Z^d} C_{0x}|x|^2$ is integrable. Our focus is on the Quenched Invariance Principle (QIP) which we establish in all $d\ge3$ by a combination of corrector methods and heat-kernel technology. In particular, a QIP thus holds for random walks on long-range percolation graphs with exponents larger than $d+2$ in all $d\ge3$, provided all nearest-neighbor edges are present. We then show that, for long-range percolation with exponents between $d+2$ and $2d$, the corrector fails to be sublinear everywhere. Similar examples are constructed also for nearest-neighbor, ergodic conductances in $d\ge4$ under the conditions close to, albeit not exactly, complementary to those of the recent work of S. Andres, M. Slowik and J.-D. Deuschel.