Sachverhalt: Mit Verfügung vom 10. November 1995 lehnte die IV-Stelle des Kantons Appenzell Ausserrhoden das Gesuch von D._ (geb. 1965) um IV-Leistungen ab. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht von Appenzell Ausserrhoden mit Entscheid vom 19. Juni 1996 ab. Auf Verwaltungsgerichtsbeschwerde hin wies das Eidgenössische Versicherungsgericht die Sache mit Urteil vom 29. September 1999 zu näheren Abklärungen im Sinne der Erwägungen an das kantonale Gericht zurück. Dieses lehnte den Leistungsanspruch von D._ mit Entscheid vom 22. November 2000 erneut ab. Die dagegen erhobene Verwaltungsgerichtsbeschwerde wies das Eidgenössische Versicherungsgericht mit Urteil vom 29. April 2002 ab. Auf Grund eines neuen Gesuchs lehnte die IV-Stelle den Rentenanspruch von D._ mit Verfügung vom 15. Januar 2003 ab. Diese Verfügung bestätigte die IV-Stelle mit Einspracheentscheid vom 18. Juli 2003. Die hiegegen eingereichte Beschwerde wies das Verwaltungsgericht von Appenzell Ausserrhoden mit Entscheid vom 24. März 2004 ab. D._ lässt Verwaltungsgerichtsbeschwerde führen und beantragen, die Sache sei zur Neubeurteilung an die IV-Stelle zurückzuweisen. Die IV-Stelle schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde, während das Bundesamt für Sozialversicherung auf eine Vernehmlassung verzichtet. 