To speed up the computation of shortest path distances between pairs of query nodes in a weighted graph, it is common to precompute a distance oracle. One of the most successful of these oracles is Hub Labeling (HL). Its good practical performance spurred research on the complexity of different HL variants, their structural properties, and suitable construction algorithms. Landmark Hub Labeling (LHL) is a generalization of HL. It enables the construction of distance oracles with similar query time but smaller space consumption than HL, which is an important aspect for practical usability. However, the complexity of LHL has not been thoroughly investigated so far. In this paper, we provide a complete picture of the complexity landscape of different LHL variants. Surprisingly, the only known HL variant for which a minimum-size oracle can be computed in polynomial time (namely ranked hierarchical HL) turns out to be NP-hard when generalized to LHL. We complement our hardness results with suitable approximation algorithms for all studied LHL variants based on novel structural insights.