High dimensional interpolation fails for >4 dimensions?

The attached notebook shows that interpolation can only work on scalar data in up to 3 dimensions (that are not structured over a grid). The following code runs:

(*interpolation works with 4D data*)
d = RandomReal[{0, 10}, {1000, 4}];
f = Interpolation[d, InterpolationOrder -> 1]
f[5, 5, 5]

But it doesn’t work with higher dimensional unstructured data. The following code fails:

(*interpolation fails with 5D data*)   
d = RandomReal[{0, 10}, {1000, 5}];
f = Interpolation[d, InterpolationOrder -> 1]
f[5, 5, 5, 5]

Any idea why? And is there an easy fix?

I believe it’s because the meshing utilities do not handle the construction of meshes above dimension 3. This is not documented under Interpolation, but one finds the restriction mentioned elsewhere. For instance:

From the documentation for DiscretizeRegion:

The region reg can be anything that is ConstantRegionQ and RegionEmbeddingDimension less than or equal to 3.