La ley del medio excluido es una ley que se utiliza para los tipos de proposiciones que solemos considerar verdaderas o falsas, por ejemplo, proposiciones aritméticas como "Todos los números pares son cuadrados". Estamos muy familiarizados con otros tipos de proposiciones en las que no se aplica. Por ejemplo, no es ni verdadero ni falso que yo esté en el salón, ya que podría estar en parte dentro y en parte fuera; no es ni verdadero ni falso que exista un dios porque primero tendríamos que ponernos de acuerdo sobre lo que significaría que existiera un dios, lo que probablemente resultaría difícil; y no es ni verdadero ni falso que Darth Vader esté muerto porque depende de futuras películas.
Así que no hay nada misterioso en que se restrinja la aplicabilidad de la ley del medio excluido. Lo que resulta confuso en el caso que mencionas es que, a primera vista, la frase "Esta proposición es falsa" parece una proposición en el ámbito de la lógica, en la que suponemos que se cumple la ley del medio excluido. Pero esto es una ilusión: en realidad es una proposición del lenguaje natural que utiliza el hecho de que el lenguaje natural tiene deícticos como "esto" para establecer la referencia y la autorreferencia. Los números y las proposiciones lógicas no se refieren a sí mismos. Así que el problema no está en creer en la ley del medio excluido para los números y la lógica, sino en identificar erróneamente esta proposición del lenguaje natural como una proposición puramente lógica.
Ahora bien, la idea fundamental que utilizó Gödel para demostrar su primer teorema de incompletitud es hacer que los números y las proposiciones lógicas se refieran a sí mismos después de todo, en cierto sentido. Al hacer esto, demostró que un sistema formal suficientemente potente es inconsistente o incompleto, es decir, o bien es inútil o bien hay proposiciones que no puede probar ni refutar. Por lo tanto, no existe una ley del medio excluido para la demostrabilidad en los sistemas formales: todo sistema formal suficientemente potente viola esta "ley". Pero eso no significa que estas proposiciones formalmente indecidibles no sean ni verdaderas ni falsas -sólo se necesita un metasistema que pueda razonar sobre el primer sistema para poder probarlas, porque intentar que el sistema razone sobre sí mismo llevaría al mismo tipo de inconsistencias autorreferenciales que considerar "Esta proposición es falsa" como una proposición lógica.
P.D. : Como ha señalado Asaf, el primer teorema de incompletitud de Gödel sólo se aplica a los sistemas formales que son recursivamente enumerables (es decir, cuyos axiomas y reglas de inferencia puede enumerar un algoritmo).
