A

"De quoi j'ai l'air?" does not really mean "How do I look?". "What do I look like?" is the correspondent English question. If you consider possible answers to that question you'll find returns such as those;

{On dirait/Vous avez l'air de} quelqu'un qui n'as pas dormi du tout et qui tient à peine debout; votre démarche est chancelante.

• You look like someone who hasn't slept at all and who can barely stand on his feet; your gait is very unsteady.

{On dirait/Vous me paraissez être} une fille qui n'as aucune notion de maquillage correct ou bien une fille qui est sur le point de faire une répétition dans une pièce de théatre .

• To me you appear to be a girl who has no notion of making up properly or who is ready to rehearse a part in a piece of theater.

Tu donne l'impression d'un joueur de football américain avec tout ce rembourrage sous tes vêtements. C'est ça! C'est l'apparence que je voulais avoir.

• You look like an american football player with all those stuffings under your clothes. Yes! That's the appearance I wanted to give myself.

"How do I look?" corresponds rather to a question as "Comment me trouve-tu?/Comment me trouvez-vous?"; less usual, but closer to the English is "Quel effet je fais?", "Quelle impression je donne?"

Answers can be as the following samples;

• Tu as l'air normalle, propre, comme d'habitude! Ne te tracasse pas.

• Vous avez l'air un peu débraillé avec cette chemise qui dépasse de votre pantalon derrière; c'est vraiment ce que vous voulez?

• Vous paraissez un peu guindé mais il ne le remarqueront pas.

• Comment le trouve tu après ces deux rounds? (How does he look after those two rounds?) Still in great shape, it's going to be a great match!

• Vous paraissez vieux mais très alerte.

"Avoir l'air de" does not mean the same thing in plain statements and in questions.

If you ask "De quoi ont-ils l'air?" it can only be on the level of physical appearance. No one will answer by "Ils ont l'air d'en avoir par dessus la tête."; that refers to an attitude having to do with a person's morale; to elicit an answer of this sort you have to ask another question, as for instance, "Comment se sentent-ils?" (How are they feeling?); you can then answer using "avoir l'air de", which means "to give the impression that"; this is because "avoir l'air de" is used to say "give an impression" both for "physical appearances" and as well for moral appearances or intellectual ones;

examples

Elle avait l'air de savoir ce qu'elle disait. Nous avions l'air d'être honnêtes. Ils avaient l'air d'être de pieux chrétiens.

B

"Il a l'air plus vieux qu'il l'est." is not said; "l" can have for antecedent only "vieux" and so what's being said is "Il a l'air plus vieux qu'il est vieux."; but "il est vieux" does not stipulate how old, so that's got no sense. It is necessary to turn that differently and one would say things such as "Il fait plus vieux que son âge.", "Il a l'air plus vieux que l'âge qu'il a vraiment.", "Il a l'air plus vieux que son âge."

C

"la dame m'a dit que j'avais l'air d'être venu de courir." is not correct; you can say

"La dame m'a dit que j'avais l'air de quelqu'un qui venait de courir." or
"La dame m'a dit que j'avais l'air d'avoir couru.".

(There are possibly other ways to say that.)

Why you can't say "avoir l'air de venir de" I suppose is because of the tense value of the verb "venir"; this verb has a modal function, that of indicating the recent past, that is the tense of an action that has just taken place, whereas "avoir l'air" connotes only a possibility, a very likely possibility, but yet, basically, nothing but a possibility. That makes its use impossible with all the conjugated forms of "venir de" in the indicative; that is posssibly the reason why it is not used either in the infinitive mood although in this mood it seems there is no problem; the reason would be then a matter of usage induced by the grammatical context; that explanation, however, is only a personal attempt at explanation that I find worth of consideration.

You'll notice that when the verb is not the modal verb then there is no problem;

Elle avait l'air de venir du froid.
Ces phrases ont l'air de venir tout droit de la bible.

"J'avais l'air que je venais de courir." is not correct either; if you absolutely want to use "venir de" another form than "avoir l'air de" is necessary; those are natural ways of say it;

La dame m'a dit qu'il lui semblait que je venais de courir.
…qu'elle croyait que je venais de courir.