I wonder if this is a problem at the product level... I'm thinking that if the fulfill button isn't showing on an order, it might mean the product has "this is a physical product" unchecked in the product page.
If fulfill is showing but then fulfill with amazon marketplace web button isn't showing, I would look into the product page as well to make sure it's still showing inventory managed by amazon marketplace web.
If neither of those work and you want some help, I can send a collaborator request to take a quick look for you to make sure everything is connected correctly (I do a lot of work with FBA and Shopify).
My best guess without seeing is it's a setting on the product level.