Given an x and z coordinate how is it possible to check which of two triangles it's over and get the y coordinate (elevation)?

This is for a heightmap.

I was using bilinear interpolation but it doesn't follow the polygons in cases where the two triangles don't follow one plane.

I assume the two triangles lie in a square grid-cell and are connected by a single edge?

If so, first check on which side of the connecting edge the point lies: dot(point - pointOnEdge, cross(float3(0, 1, 0), edge) > 0).

Then plug the x and y values into the overlapping triangle's plane equation. (a*x + b*y + c*z = d) => y = (a*x + c*z - d) / -b.