My solution was to store the term order as metadata for the post.
//reset terms
if( is_array( $_POST['genres'] ) && count( $_POST['genres'] ) ){
$_POST['genres_order'] = ( $_POST['genres'] = array_map( 'intval', $_POST['genres'] ) );
wp_set_object_terms( $_POST['ID'], $_POST['genres'], 'nv_genre', false ); //will replace any previous genres
}
Then when I retrieve the terms I can order them by id. More detailed explaination here: Control term order on a per-post basis
