Is there any geometry where the triangle inequality fails?

There are people who seriously study quasi-normed spaces. The most natural examples are $\ell_p$ spaces for p strictly between 0 and 1 (the "norm" given by the usual formula and the distance given by the norm of the difference). Although these spaces do not satisfy the triangle inequality, you get an inequality of the form $\|x+y\|\leq C(\|x\|+\|y\|)$.

What do you mean by "denial"? There is the hoary old story of the researcher who wrote an entire thesis on the properties of antimetric spaces, ie spaces where $d(a,b) \ge d(a,c) + d(b,c)$ for all $a,b$ and $c$... without realising that any such space must consist of at most a single point!

Any geometry modelled on non-positive definite spaces will yield an example. As Sergei Ivanov mentioned in the comments, an $n$-dimensional Lorentz geometry is modelled on the indefinite space $\mathbb{R}^{1,n-1}$, and there are tangent vectors of negative norm, hence paths of negative length squared. These appear a lot in special and general relativity, where one direction is time, and the rest are space.

Another example is the root space of an affine Kac-Moody Lie algebra, which has a singular metric (i.e., there is a line that is perpendicular to everything). It embeds as the codimension 1 subspace of a Lorentz space that is perpendicular to a lightlike (i.e., nonzero norm 0) vector. Its geometry comes into play when considering the affine Weyl group, which acts on this space by reflections. For reasons of sanity, one typically studies the action by using the Lorentz embedding to extend it to a group of hyperbolic reflections that fix a boundary point, and considering the induced action on a horocycle (which has Euclidean geometry).