Hay varias cosas que puede crear problemas con el JavaScript de la pregunta:

- Se hace `parseFloat` de los campos incluso cuando están vacíos, lo que resulta en un NaN y un total no esperado. Lo ideal sería que si el campo está vacío y el valor va a ser NaN se utilizase 0 en su lugar. 

    Para lograr esto añade un `|| 0` en la asignación:

        var TextBox1 = parseFloat(document.getElementById("txt1").value) || 0;
        var TextBox2 = parseFloat(document.getElementById("txt2").value) || 0;
        var TextBox3 = parseFloat(document.getElementById("txt3").value) || 0;

- Se hace `parseFloat` sin preprocesar el campo, lo cual puede dar problemas con el formato que usas. Por ejemplo: imagina que tienes el valor 1234, que formateado se ve 1.234; cuando haces parseFloat de 1.234, el navegador considera que 1 es la parte entera y 234 son decimales, cuando realmente lo que quieres es todo como parte entera. 

    Para solucionar esto, utiliza `replace()`  de la misma manera que lo usas en la función de formato, de este modo se estará procesando correctamente como entero:

        var TextBox1 = parseFloat(document.getElementById("txt1").value.replace(/\./g, ''));
        var TextBox2 = parseFloat(document.getElementById("txt2").value.replace(/\./g, ''));
        var TextBox3 = parseFloat(document.getElementById("txt3").value.replace(/\./g, ''));

- Cuando se cambia el valor del total, no se está  formateando como los otros campos. Simplemente añade una llamada a la función `format` pasándole como valor el elemento con el total:

        format(document.getElementById("txt4"));

Combinando todos estos cambios, el código se vería como en esta demo:

<!-- begin snippet: js hide: false -->

<!-- language: lang-js -->

    function agregar_numero() {
      // quitas los puntos (para evitar problemas con los decimales) e inicializa a 0 si el campo esta vacio 
      var TextBox1 = parseFloat(document.getElementById("txt1").value.replace(/\./g, '')) || 0;
      var TextBox2 = parseFloat(document.getElementById("txt2").value.replace(/\./g, '')) || 0;
      var TextBox3 = parseFloat(document.getElementById("txt3").value.replace(/\./g, '')) || 0;
      var result = TextBox1 + TextBox2 + TextBox3;
      result.toFixed(2);
      document.getElementById("txt4").value = result;
      
      // formatea el resultado para que aparezca igual que los otros numeros
      format(document.getElementById("txt4"));
    }

    function format(input) {
      var num = input.value.replace(/\./g, '');
      if (!isNaN(num)) {
        num = num.toString().split('').reverse().join('').replace(/(?=\d*\.?)(\d{3})/g, '$1.');
        num = num.split('').reverse().join('').replace(/^[\.]/, '');
        input.value = num;
      }
      else {
        alert('Solo se permiten numeros');
        input.value = input.value.replace(/[^\d\.]*/g, '');
      }
    }

<!-- language: lang-html -->

    <input id="txt1" class="test" Width="70px" onkeyup="agregar_numero();format(this)" onchange="format(this)"/>
    <input id="txt2" class="TextBoxBorder" Width="70px" onkeyup="agregar_numero();format(this)" onchange="format(this)"/>
    <input id="txt3" class="TextBoxBorder" Width="70px" onkeyup="agregar_numero();format(this)" onchange="format(this)"/>
    <br />
    Total<br />
    <input id="txt4" class="TextBoxBorder" Width="70px" onkeyup="format(this)"/>



<!-- end snippet -->

--------------------------------------

**Actualización:** Me preguntaron cómo se haría algo similar pero en lugar de utilizando puntos, usando comas para la separación de los miles y dejando el punto para los decimales. Por ejemplo, para admitir números como 123,123,123.12

Los cambios para lograr eso son sencillos:

- Actualizar todas las sustituciones y expresiones regulares de . a , (hay bastantes).
- En la función que formatea los números:
  - Separar la parte entera y los decimales
  - Hacer todas las operaciones de formateo con la parte entera
  - Volver a añadir la parte decimal después de formatear la entera

El resultado final quedaría así:

<!-- begin snippet: js hide: false -->

<!-- language: lang-js -->

    function agregar_numero() {
      // quitas los puntos (para evitar problemas con los decimales) e inicializa a 0 si el campo esta vacio 
      var TextBox1 = parseFloat(document.getElementById("txt1").value.replace(/,/g, '')) || 0;
      var TextBox2 = parseFloat(document.getElementById("txt2").value.replace(/,/g, '')) || 0;
      var TextBox3 = parseFloat(document.getElementById("txt3").value.replace(/,/g, '')) || 0;
      var result = TextBox1 + TextBox2 + TextBox3;
      //console.log(TextBox1 + "__" + TextBox2 + "__" + TextBox3 + "__" + result);
      result.toFixed(2);
      document.getElementById("txt4").value = result;

      // formatea el resultado para que aparezca igual que los otros numeros
      format(document.getElementById("txt4"));
    }

    function format(input) {
      var num = input.value.replace(/\,/g, '');
      var decimales = "";
      if (num.indexOf(".") >= 0) { 
        decimales = "." + num.split(".")[1].substring(0,2); // sólo nos quedamos con los dos primeros decimales
        num = Math.floor(num); // redondeamos hacia abajo para quedarnos con la parte entera
      }
      if (!isNaN(num)) {
        num = num.toString().split('').reverse().join('').replace(/(?=\d*\,?)(\d{3})/g, '$1,');
        // añadir los decimales al final!
        num = num.split('').reverse().join('').replace(/^[\,]/, '') + decimales;
        input.value = num;
      }
      else {
        alert('Solo se permiten numeros');
        input.value = input.value.replace(/[^\d\,\.]*/g, '');
      }
    } 

<!-- language: lang-html -->

    <input id="txt1" class="test" Width="70px" onkeyup="agregar_numero();format(this)" onchange="format(this)"/>
    <input id="txt2" class="TextBoxBorder" Width="70px" onkeyup="agregar_numero();format(this)" onchange="format(this)"/>
    <input id="txt3" class="TextBoxBorder" Width="70px" onkeyup="agregar_numero();format(this)" onchange="format(this)"/>
    <br />
    Total<br />
    <input id="txt4" class="TextBoxBorder" Width="70px" onkeyup="format(this)"/>

<!-- end snippet -->