Apesar do novo botão ser um elemento com a mesma tag, classe e conteúdo, ele **não é o mesmo elemento**, e portanto ele não tem o evento de clique que o elemento original tinha.

Veja aqui como o botão muda depois que você o remove e adiciona outro:

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

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

    let app = document.querySelector('.app');
    let button = document.querySelector('.btn');
    let newButton = '<button class="btn">Clique-me</button>';

    button.addEventListener('click', (e) => {
        // antes de remover, o botão dentro de "app" é o mesmo que "button"
        console.log(app.querySelector('button') === button); // true
        app.innerHTML = '';
        app.insertAdjacentHTML('beforeend',newButton);
        // depois de remover e adicionar outro, o botão dentro de "app" não é mais o mesmo que "button"
        console.log(app.querySelector('button') === button); // false
    });

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

    <div class="app">
      <button class="btn">Clique-me</button>  
    </div>

<!-- end snippet -->

Depois de clicar no botão, ele vai mostrar no console `true` (pois o botão que está dentro da `div` é o original) e depois `false` (pois o novo botão que foi inserido não é mais o mesmo elemento - ou seja, se clicar na segunda vez ele já não imprime mais nada, pois o novo botão não tem nenhum evento de clique associado).

Segundo a [documentação de `insertAdjacentHTML`](https://developer.mozilla.org/en-US/docs/Web/API/Element/insertAdjacentHTML), é feito o *parsing* do HTML e os nós resultantes deste *parsing* são inseridos no [DOM](https://pt.stackoverflow.com/q/40852/112052). O que acontece é que esses nós novos não tem nenhuma relação com os anteriores (mesmo que o conteúdo do HTML seja idêntico).

---
# Solução

Em vez de adicionar o evento no botão, uma alternativa é usar [*event delegation*][1] e colocar o evento na `div`:

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

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

    let app = document.querySelector('.app');
    let button = document.querySelector('.btn');
    let newButton = '<button class="btn">Clique-me</button>';

    app.addEventListener('click', (e) => {
        const element = e.target; // pega o elemento que foi clicado
        // verifica se o elemento clicado é o botão que tem a classe btn
        if (element.nodeName == 'BUTTON' && element.classList.contains('btn')) {
            alert('removido');
            app.innerHTML = newButton;
        }
    });

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

    <div class="app">
      <button class="btn">Clique-me</button>  
    </div>

<!-- end snippet -->

Ou seja, o evento de clique é para toda a `div` (inclusive qualquer elemento dentro dela), mas no *callback* eu verifico se o elemento clicado é o botão. Para saber melhor como funciona o *event delegation*, [leia aqui](https://pt.stackoverflow.com/a/333053/112052).

Note também que nem precisa de `insertAdjacentHTML`, pois antes você seta o `innerHTML` para a string vazia, e isso faz com que todo o conteúdo da `div` seja apagado (`insertAdjacentHTML` faz mais sentido se você quisesse manter os elementos da `div` e quisesse inserir o novo na posição específica, mas como a `div` estará vazia, não faz diferença). Sendo assim, é mais fácil simplesmente substituir o `innerHTML` diretamente.

---
### Solução não tão boa

Uma solução pior e mais trabalhosa é adicionar o _listener_ no novo elemento. Em vez de criar o elemento como uma string, pode ser feito assim:

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

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

    function removeBotaoCriaOutro() {
        const novo = document.createElement('button');
        novo.classList.add('btn');
        novo.textContent = 'Clique-me';
        // *** adicionar o evento no novo botão ***
        novo.addEventListener('click', removeBotaoCriaOutro);

        alert('removido');
        app.innerHTML = '';
        app.appendChild(novo); // como o div está vazio, pode adicionar assim
    }

    let app = document.querySelector('.app');
    let button = document.querySelector('.btn');

    button.addEventListener('click', removeBotaoCriaOutro);

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

    <div class="app">
      <button class="btn">Clique-me</button>  
    </div>

<!-- end snippet -->

Mas se quiser manter o novo botão como string, também pode ser:

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

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

    function removeBotaoCriaOutro() {
        let novo = document.createElement('template');
        novo.innerHTML = '<button class="btn">Clique-me</button>';
        novo = novo.content.firstChild;
        novo.addEventListener('click', removeBotaoCriaOutro);

        alert('removido');
        app.innerHTML = '';
        app.appendChild(novo); // como o div está vazio, pode adicionar assim
    }

    let app = document.querySelector('.app');
    let button = document.querySelector('.btn');

    button.addEventListener('click', removeBotaoCriaOutro);

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

    <div class="app">
      <button class="btn">Clique-me</button>  
    </div>

<!-- end snippet -->

Mas me parece um trabalho desnecessário ter que adicionar o evento toda hora, pois usar *event delegation* é uma solução bem mais simples para este caso, já que basta adicionar o evento uma vez na `div` e ela cuida de verificar se o elemento clicado é o botão que queremos.

Desta forma, quaisquer elementos novos que forem adicionados já "ganham de graça" o *event handler* da `div`.

---
<sup>Eu só questiono a utilidade de remover um elemento para adicionar outro idêntico logo em seguida (se foi para fins de aprendizado, ainda vai...)</sup>


  [1]: https://davidwalsh.name/event-delegate