Can not add admin notices from the edit_user_profile_update hook (notices not being displayed)?

WordPress redirects you back to the user-edit.php page upon successful user update, so while the admin_notices has yet been fired in your sulock_save_profile_fields(), the message (your custom admin notice) is never displayed because of the redirection.

And one way to fix it, is by filtering the redirect URL via the wp_redirect filter:

// In sulock_save_profile_fields()
if ( update_user_meta( $user_being_edited_id, 'sulock_permanently_locked', $permlock ) ) {
    update_user_meta( $user_being_edited_id, 'sulock_permlock_meta', new Sulock\LockMeta() );

    add_filter( 'wp_redirect', function( $location ) use ( $permlock ) {
        return add_query_arg( 'permlock', $permlock, $location );
    } );
}

Then hook to load-user-edit.php which is fired when the user-edit.php page is loaded, and add the admin notice from there: (the updated item below is set by WordPress)

add_action( 'load-user-edit.php', function(){
    if ( ! empty( $_GET['updated'] ) && isset( $_GET['permlock'] ) ) {
        if ( $_GET['permlock'] ) {
            sulock_admin_notice(__('Message here.', SULOCK_TEXTDOMAIN), 'notice notice-warning');
        } else {
            sulock_admin_notice(__('Message here.', SULOCK_TEXTDOMAIN), 'notice notice-warning');
        }
    }
} );

Alternatively, you could (or might want to) use the transients API:

// In sulock_save_profile_fields()
if ( update_user_meta( $user_being_edited_id, 'sulock_permanently_locked', $permlock ) ) {
    update_user_meta( $user_being_edited_id, 'sulock_permlock_meta', new Sulock\LockMeta() );

    set_transient( 'su_updated', [ 'permlock' => $permlock ], 30 );
}

And the hook:

add_action( 'load-user-edit.php', function(){
    if ( ! empty( $_GET['updated'] ) ) {
        $data = get_transient( 'su_updated' );
        if ( $data && $data['permlock'] ) {
            sulock_admin_notice(__('Message here.', SULOCK_TEXTDOMAIN), 'notice notice-warning');
        } elseif ( $data ) { // the transient exists (not expired)
            sulock_admin_notice(__('Message here.', SULOCK_TEXTDOMAIN), 'notice notice-warning');
        }
    }
} );