Just use wp_register_style() and wp_enqueue_style() correctly.
Register your stylesheet on wp_loaded, enqueue it on wp_enqueue_scripts.
add_action( 'wp_loaded', function() {
wp_register_style(
'fontawesome',
'//maxcdn.bootstrapcdn.com/font-awesome/4.1.0/css/font-awesome.min.css'
);
});
add_action( 'wp_enqueue_scripts', function() {
wp_enqueue_style( 'fontawesome' );
});
When someone tries to call wp_enqueue_style() with an URL, WordPress will try to register it automatically, doing the work of wp_register_style() behind the curtains. But that will fail if the $handle is already registered.
Always register scripts and stylesheet on wp_loaded. Never use wp_enqueue_style() and wp_enqueue_script() with the second parameter.
Do not fiddle with priorities here. The conflicting plugin might change its own priority, and you start running behind again.