open problem - How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.

Here are Vinay Deolalikar's paper, and Richard Lipton's first post about it, and the wiki page on polymath site summarizing the discussions about it. His approach is based on descriptive complexity.

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 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:
https://mathoverflow.net/questions/34947/when-would-you-read-a-paper-claiming-to-have-settled-a-long-open-problem-like-p
https://mathoverflow.net/questions/34953/whats-wrong-with-this-proof-closed

Discussion on meta:
http://tea.mathoverflow.net/discussion/590/whats-wrong-with-this-proof/