Register script in one plugin, and enqueue it in another

Prioritize your actions, so the register_style function runs first. (notice the third parameter in the add_action function)

add_action( 'wp_enqueue_scripts', 'other_register_styles', 11 );
function other_register_styles() {
       wp_register_style( 'style', PATH . 'assets/css/style.min.css' );
       wp_enqueue_style( 'style' ); // Working as expected

       wp_enqueue_style( 'fontawesome' ); // Currently not working!
}

The default priority is 10, so you just need to add 11 to other_register_styles.