Template override not working for search-results-message.php

I’ll fix that in the next version. Meanwhile, you can do this:

add_action( 'init', function() {
    global $wp_filter;
    unset( $wp_filter['wp_ajax_relevanssi_live_search_messages'] );
    unset( $wp_filter['wp_ajax_nopriv_relevanssi_live_search_messages'] );

    add_action( 'wp_ajax_relevanssi_live_search_messages', 'custom_get_ajax_messages_template' );
    add_action( 'wp_ajax_nopriv_relevanssi_live_search_messages', 'custom_get_ajax_messages_template' );
}, 11 );

function custom_get_ajax_messages_template() {
    ob_start();
    include __DIR__ . '/templates/search-results-messages.php';
    $content = ob_get_clean();
    wp_send_json( $content );
}

2.2.0 is out now, so you should be able to just override the template.