Nice URLs for a Custom Post Type List with a Shared Custom Taxonomy?

For the first preference, you’d need to filter in additional rewrite rules like so;

function __extra_country_rewrite_rules( $rules )
{
    global $wp_rewrite;
    if ( !isset( $wp_rewrite ) )
        $wp_rewrite = new WP_Rewrite;

    $m1 = $wp_rewrite->preg_index(1); // preg match backreferences
    $m2 = $wp_rewrite->preg_index(2);
    $m3 = $wp_rewrite->preg_index(3);

    $rules['country/([^/]+)/([^/]+)s/feed/(feed|rdf|rss|rss2|atom)/?$'] = "index.php?country=$m1&post_type=$m2&feed=$m3";
    $rules['country/([^/]+)/([^/]+)s/(feed|rdf|rss|rss2|atom)/?$'] = "index.php?country=$m1&post_type=$m2&feed=$m3";
    $rules['country/([^/]+)/([^/]+)s/page/?([0-9]{1,})/?$'] = "index.php?country=$m1&post_type=$m2&paged=$m3";
    $rules['country/([^/]+)/([^/]+)s/?$'] = "index.php?country=$m1&post_type=$m2";

    return $rules;
}
add_filter( 'country_rewrite_rules', '__extra_country_rewrite_rules' );

The second one is less dynamic, as you’d need to hardcode the post types in your rewrites (there is no initial ‘indentifier’ in the URL, unlike ‘country’ in the former).

function __extra_country_rewrite_rules( $rules )
{
    global $wp_rewrite;
    if ( !isset( $wp_rewrite ) )
        $wp_rewrite = new WP_Rewrite;

    $m1 = $wp_rewrite->preg_index(1); // preg match backreferences
    $m2 = $wp_rewrite->preg_index(2);
    $m3 = $wp_rewrite->preg_index(3);

    $rules["(event|contact)s/country/([^/]+)/feed/(feed|rdf|rss|rss2|atom)/?$"] = "index.php?post_type=$m1&country=$m2&feed=$m3";
    $rules["(event|contact)s/country/([^/]+)/(feed|rdf|rss|rss2|atom)/?$"] = "index.php?post_type=$m1&country=$m2&feed=$m3";
    $rules["(event|contact)s/country/([^/]+)/page/?([0-9]{1,})/?$"] = "index.php?post_type=$m1&country=$m2&paged=$m3";
    $rules["(event|contact)s/country/([^/]+)/?$"] = "index.php?post_type=$m1&country=$m2";

    return $rules;
}
add_filter( 'rewrite_rules_array', '__extra_country_rewrite_rules' );

You’ll need to flush your permalinks for changes to take effect (just visit the Permalinks settings page once the code has been added).

If you find that things still aren’t functioning correctly, update your question with the code you use to register your post types & custom taxonomies.