El control del formulario lo puedes hacer también con html5 usando los atributos: `required` para que el campo sea obligatorio, `pattern=".*\S+.*"` para no aceptar valores de espacios en blanco sin letras, `title="No es un nombre valido"` para el mensaje de error a mostrar en caso de que el nombre contenga solo espacios en blanco. Usando esto ya puedes deshacerte de los primeros dos `if`, aun así, como no sé si es un requerimiento utilizar JavaScript para eso, incluyo ambas maneras.

Tu código presenta algunos errores, como por ejemplo:

`var fila = "<tr><td>" + nombre + "</td><td>" + apellido + "</td>" + "</td></tr>";`

Que debería ser:

`var fila = "<tr><td>" + nombre + "</td><td>" + apellido + "</td></tr>";`

Te recomiendo comparar mi código al tuyo para encontrar los otros.

Formulario que valida sin js:

    <form id="formulario" action="" onsubmit='return false'>
        <input type="text" placeholder="Nombre" id="nombre" required pattern=".*\S+.*" title="No es un nombre valido">
        <input type="text" placeholder="Apellido" id="apellido" required pattern=".*\S+.*" title="No es un nombre valido">
        <button type="submit" onclick="Guardar()">Añadir</button>
        <button type="submit" onclick="Eliminar()">Eliminar</button>
    </form>

> El atributo `onsubmit='return false'` sirve para que el formulario no envíe los datos evitando así que la página se recargue y cancele el contenido de la tabla, ya que para que funcione esta forma de validación es necesario que los botones sean de tipo `submit`.

Código completo con un formulario que se valida usando js y cumple con el resto de los puntos especificados:

<!-- begin snippet: js hide: false console: true babel: false -->

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

    function Personas() {
        /* Devuelve las personas de la tabla */

        let personas = [];
        for (let i = 0; i < tabla.rows.length; i++) {
            // Elimina espacios en blanco y mayusculas
            personas.push(document.getElementById('tabla').rows[i].innerText.toLowerCase().replace(/\s+/g, ''));
        }
        return personas
    };

    function LimpiarFormulario() {
        /* Limpia los campos y enfoca el primer campo */

        document.getElementById('formulario').reset();
        document.getElementById('nombre').focus();
    };

    function Control(guardar=false,eliminar=false) {
        /* Controla los campos input */

        var nombre = document.getElementById('nombre');
        var apellido = document.getElementById('apellido');
        var alertas = document.getElementById('alertas');

        if (nombre.value.trim() == '') {
            alertas.innerHTML = 'No puedes dejar el nombre vacio';
            nombre.focus();
            return 1;
        } else if (apellido.value.trim() == '') {
            alertas.innerHTML = 'No puedes dejar el apellido vacio';
            apellido.focus();
            return 1;
        } else if (guardar && Personas().includes(nombre.value.trim().concat(apellido.value.trim()).toLowerCase())) {
            // La persona ya esta en la tabla               
            alertas.innerHTML = nombre.value + ' ' + apellido.value + 'ya esta en la lista';
            LimpiarFormulario()
            return 1;
        } else if (eliminar && !Personas().includes(nombre.value.trim().concat(apellido.value.trim()).toLowerCase())) {
            // La persona no esta en la tabla             
            alertas.innerHTML = nombre.value + ' ' + apellido.value + 'no se encuentra en la lista';
            LimpiarFormulario()
            return 1;
        } else {
            return 0;
        }
    };

    function Guardar() {
        /* Añade una persona a la tabla */

        if (Control(guardar=true,eliminar=false)) {
            // Control no superado
        } else {
            let btn = document.createElement("TR");
            btn.innerHTML = "<tr><td>" + nombre.value.trim() + "</td><td>" + apellido.value.trim() + "</td></tr>";
            document.getElementById("tabla").appendChild(btn);
            LimpiarFormulario();
            alertas.innerHTML = '&nbsp;';
        }
    }

    function Eliminar() {
        /* Elimina una persona de la tabla */

        if (Control(guardar=false,eliminar=true)) {
            // Control no superado
        } else {
            let indice = Personas().indexOf(nombre.value.trim().concat(apellido.value.trim()).toLowerCase());
            document.getElementById('tabla').deleteRow(indice);
            LimpiarFormulario();
            alertas.innerHTML = '&nbsp;';
        }
    }

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

    <div class="container">  
        <div id="alertas">&nbsp;</div>
        <br>
        <form id="formulario" action="">
            <input type="text" placeholder="Nombre" id="nombre">
            <input type="text" placeholder="Apellido" id="apellido">
            <button type="button" onclick="Guardar()">Añadir</button>
            <button type="button" onclick="Eliminar()">Eliminar</button>
        </form>
        <br>
        <table border="1">
            <thead>
                <tr>
                    <th>Nombre</th>
                    <th>Apellido</th>
                </tr>
            </thead>
            <tbody id="tabla">
            </tbody>
        </table>
    </div>

<!-- end snippet -->