Solo necesitas agregar una función para escuchar cambios en el campo, el evento `input` podría ser suficiente. Por cierto, cambié la forma de agregar y eliminar clases, usando la API de jQuery porque no tiene sentido mezclar con Javascript puro.


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

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

    function EnviarInformacion() {
        let Contacto = $("#Contacto").val();
        // Eliminar clase antes de validar
        $("#alert").removeClass("show");
        if (/^(([^<>()[\]\.,;:\s@\"]+(\.[^<>()[\]\.,;:\s@\"]+)*)|(\".+\"))@(([^<>()[\]\.,;:\s@\"]+\.)+[^<>()[\]\.,;:\s@\"]{2,})$/i.test(Contacto)) {
            //Codigo de validacion aquí
        } else {
            // Agregar clase cuando es un correo inválido
            $("#alert").addClass("show");
        }
    }

    // Escuchar cambios en campo
    $('#Contacto').on('input', function() {
        $("#alert").removeClass("show");
    });

<!-- language: lang-css -->

    .alert {
        opacity: 0;
        transition: all 0.5s ease;
        max-height:0; /* Comienza con altura en cero */
        padding: 15px;
        margin-bottom: 20px;
        border: 1px solid transparent;
        border-radius: 4px;
    }

    .alert-danger {
        color: #a94442;
        background-color: #f2dede;
        border-color: #ebccd1;
    }

    .show {
        opacity: 1;
        max-height: 150px; /* Altura adaptable a contenido */
    }

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

    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
    <link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" rel="stylesheet"/>

    <div class="row">
                                    <div class=" col-sm-12 col-xs-12 col-md-12 col-lg-12">
                                        <br /><br />
                                        <p>
                                            <span class="ContenidoContactoMensaje">
                                                Ingresa tu correo<br />
                                            </span>
                                        </p>
                                    </div>
                                    <br />

                                </div>
                                <div class="row">
                                    <div class="col-sm-12 col-xs-12 col-md-12 col-lg-12 alinearDerecha">
                                        <div class="col-sm-6 col-xs-12 col-md-6 col-lg-6 row2">

                                            <input type="text" name="Contacto" value="" size="50" class="form-control" id="Contacto" />
                                            <div id="alert" class="alert alert-danger" style="font-family: 'Lettera Text Std';">Favor de ingresar una cuenta de correo válida.</div>
                                        </div>
                                        <div class="col-sm-6 col-xs-12 col-md-6 col-lg-6 row2">
                                            <button class="EnviarContactoDetalleProducto btn-lg" onclick="EnviarInformacion()"> Enviar</button>
                                        </div>
                                        <br />
                                    </div>

                                </div>

<!-- end snippet -->