Was machen denn diese beiden Tags dort? Führt das denn in anständigen Browsern zu keiner Fehlermeldung?

Bisher nicht. Ich habe den Code vom Grundgerüst her aus dem Netz kopiert weil das mein erstes Ajax ist. Bisher hat sich noch kein Browser beschwert.

if(xmlhttp.readyState==4 && xmlhttp.status==200){
        document.getElementById("livesearch").innerHTML=xmlhttp.responseText;
        document.getElementById("livesearch").style.display="inline";
      }

Das hier ist die Stelle, die ich meinte. Du änderst also einfach die innerHTML-Eigenschaft Deines <span>. Da wird in der Tat kein JavaScript "interpretiert". Verwende die üblichen DOM-Funktionen zum Erzeugen (document.createElement) und Einhängen (<element>.appendChild oder <element>.insertBefore). Dabei kannst Du dann auch onclick-Eigenschaften so definieren, dass sie tatsächlich "interpretiert" werden.

Dass die Ajax-Response mit innerhtml gefüllt wird habe ich bisher in allen tutorials so gesehen. Aber ich suche mal ob ich finde wie das mit der anderen Methode funktioniert...