EDIT: this This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.
One of famous barriers for separating $NP$ from $P$ is Razborov-Rudich Natural Proofs barrier. Richard Lipton remarked about his paper and the natural proofs barrier that apparently "it exploits a uniform characterization of P that may not extend to give lower bounds against circuits". A question which is also mentioned in one of the comments on Lipton's post is:
How essential is the uniformity of $P$ to his proof?
i.e is the uniformity of $P$ used in such an essential way that the barrier will not apply to it? (By essential I mean that the proof does not work for the non-uniform version.)
So here is my questions:
Are there any previous computational complexity results based on descriptive complexity that avoid the Razborov-Rudich natural proofs barrier (because of being based on descriptive complexity)?
How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?
A related question is:
What are the complexity results using uniformity in an essential way other than proofs by diagonalization?
Related closed MO posts:
Discussion on meta: