Average-case analysis of algorithms using the incompressibility method
I think that the recent constructive proof of the Lovasz Local Lemma (http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html) and Patrascu's analysis of the component size in cuckoo hashing might both qualify.  These are both stated in terms of random strings, but would also work with Kolmogorov random strings (http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).