Get the original menu item name string instead of the label

You can try to get that information by using the get_term_by() function with the relevant parameters of the menu item (namely object and object_id) :

foreach( (array) $menu_items as $key => $menu_item )
{
    // Match the menu items to your custom taxonomy:
    if( 'solutions_category' === $menu_item->object )
    {
        // Fetch the corresponding term object:
        $term = get_term_by( 'term_id', $menu_item->object_id, $menu_item->object );

        // Show the term name:
        echo $term->name;

        // Debug:
        // print_r( $term );
    }
}

Note that if you don’t want to target a special taxonomy, you can replace

    // Match your custom taxonomy:
    if( 'solutions_category' === $menu_item->object )

with

    // Match only menu items of the type "taxonomy":
    if( 'taxonomy' === $menu_item->type )

where $menu_item->type can have values like taxonomy, post_type, custom (Links), ...

The value of $menu_item->type_label gives you also further information on the menu item type.

Hope this help.