Is it possible to spontaneously break Lorentz invariance, i.e., have a Lagrangian that respects LI but a vacuum which does not? If it is possible, why isn't there even the slightest hint of the Minkowski vacuum not being Lorentz invariant? (Or in other words, would this pose another fine-tuning problem?)
Dear D-brane, yes, in principle, one could have theories that spontaneously break the Lorentz symmetry. Just add a vector field (or another non-scalar field) and some potential of the form $$(V_\mu V^\mu - v^2)^2 $$ which will drive $V_\mu$ towards a vector of the right length, i.e. $(v,0,0,0)$ which would pick a preferred reference frame at each point much like the Higgs boson picks the "right" direction in the space of doublets.
The Lorentz symmetry has been checked at an incredible accuracy, so because the breaking above would break the Lorentz symmetry and introduce Lorentz-breaking coefficients for all terms in physics, it is not just one fine-tuning. It would be a collection of dozens of fine-tuned quantities - for each term in the Lagrangian that we can measure, there would be at least one fine-tuned quantity.
As far as I can say, this is clearly excluded, at least for any microscopic value of $v$.
I find it interesting to read the other answers. It shows the great gap between high energy and condensed matter physics. If you write down a simple relativistic model for your favourite solid then it obviously should break Lorentz invariance spontaneously (both boosts and translation as well as rotation). And yes it is physical as most objects around us are in fact in their solid phase.