Very little is known about the structure of fitness landscapes.
H.A. Orr (2005; also Whitlock et al., 1995; Kryazhimskiy et al., 2009) explains that most experimental results do not actually attempt to measure the fitness landscape, but instead report just the average fitness versus time and average number of acquired adaptations versus time. This can't be used to discern epistatic interactions, or any combinatorial structure of the landscape. In general, the theory of adaptive walks has developed without reference to real data and even the most refined theories can only correspond in vague qualitative ways (see Kryazhimskiy et al., 2009 for the best example I know).
Szendro et al. (2013) surveyed the few recent experiments that conducted a methodical examination of all mutations in a subset of loci of model organisms, but most studies (6 out of 12) were able to empirically realize only small fitness landscapes of just 4 to 5 loci (so 16 to 32 vertexes), with the largest full fitness landscape having length 6 with all 64 vertexes examined (Hall et al., 2010), and the largest number of vertexes in a single study being 418 out of the possible 512 in a length 9 landscape (O’Maille et al., 2008). These are extremely small landscapes, and thus don't have much power in distinguishing proposed theoretical models.
After extensive searching, I have not been able to find examples of theorists doing worst case analysis of fitness landscapes. The closest to worst-case analysis is Orr-Gillespie theory (Gillespie, 1991; Orr, 2002; 2006; Kryazhimskiy et al., 2009) that assumes that the wild-type is still very fit after an environmental change, and so beneficial mutations are extremely rate. This allows the authors to introduce extreme value theory and consider just the asymptotic properties of distribution tails thus allowing a more general treatment with fewer parameters; in some cases leading to a full classification of adaptive trajectories (Kryazhimskiy et al., 2009). This approach is easier to relate to experiment, but unfortunately completely ignores the combinatorial structure (beyond first-order) of the fitness landscape and always just samples the next potential mutant from the tail of a distribution without taking into account how it is progressing in the landscape. Although Orr (2006) introduced the basics of fitness landscape structure, the structure was much simpler than the NK model; he used Perelson & Macken's (1995) block model with each block as completely unstructured beyond first-order.
Gillespie, J.H. (1991). The causes of molecular evolution. Oxford University Press.
Hall, D. W., Agan, M., & Pope, S. C. (2010). Fitness epistasis among 6 biosynthetic loci in the budding yeast Saccharomyces cerevisiae. Journal of Heredity, 101: S75-S84.
Kryazhimskiy, S., Tkacik, G., & Plotkin, J.B. (2009). The dynamics of adaptation on correlated fitness landscapes. Proc. Natl. Acad. Sci. USA 106(44): 18638-18643.
O’Maille, P. E., Malone, A., Dellas, N., Hess, B. A., Smentek, L., Sheehan, I., Greenhagen, B.T., Chappell, J., Manning, G., & Noel, J.P. (2008). Quantitative exploration of the catalytic landscape separating divergent plant sesquiterpene synthases. Nature Chemical Biology, 4(10): 617-623.
Orr, H.A. (2002). The population genetics of adaptation: the adaptation of DNA sequences. Evilution 56: 1317-1330.
Orr, H.A. (2005). The genetic theory of adaptation: a brief history. Nature Reviews Genetics 6(2): 119-127.
Orr, H.A. (2006). The population genetics of adaptation on correlated fitness landscapes: the block model. Evolution 60(6): 1113-1124.
Perelson, A.S., & Macken, C.A. (1995). Protein evolution of partially correlated landscapes. Proc. Natl. Acad. Sci. USA 92:9657-9661.
Szendro, I. G., Schenk, M. F., Franke, J., Krug, J., & de Visser, J. A. G. (2013). Quantitative analyses of empirical fitness landscapes. Journal of Statistical Mechanics: Theory and Experiment 2013(01): P01005.
Whitlock, M.C., Phillips, P.C., Moore, F.B.-G., & Tonsor, S.J. (1995). Multiple fitness peaks and epistasis. Annu. Rev. Ecol. Syst. 26: 601-629.