How to avoid wp_nav_menu() ID conflict?

The solution is not to call the same 'theme_location' more than once. Theme location is intended to represent an explicit location within the template.

Just register a separate 'theme_location' for each separate location within the template that you want to display a nav menu.

Consider your chosen 'theme_location' names to be semantic names, representing the template location of the menu. You could use 'primary' and 'secondary', or 'header' and 'footer', etc.:

<?php
function wpse55380_setup_theme() {

    // Register nav menu locations
    register_nav_menus( array(
        'header' => 'Header Menu',
        'footer' => 'Footer Menu'
    ) );
}
add_action( 'after_setup_theme', 'wpse55380_setup_theme' ); 

…or:

<?php
function wpse55380_setup_theme() {

    // Register nav menu locations
    register_nav_menus( array(
        'primary'   => 'Primary Header Menu',
        'secondary' => 'Secondary Header Menu'
    ) );
}
add_action( 'after_setup_theme', 'wpse55380_setup_theme' ); 

Then, it is up to the end user to assign custom menus to each Theme Location.