Let plugin check if taxonomy is already registered by another plugin

The problem is that the function is defined whether you use it or not. What you want is the PHP function function_exists

if ( !taxonomy_exists( 'my_taxonomy' )
   && !function_exists('register_taxonomy_my_taxonomy') 
) {
    add_action( 'init', 'register_taxonomy_my_taxonomy' );
    function register_taxonomy_my_taxonomy() {
        ...
}

You should be able to create a reusable library (class) that would take care of this problem more elegantly, though.