So our node is online, channels have sufficient inbound/outbound liquidity, and other wallets work. Many times lightning payments fail because of pathfinding issues between the nodes.

Your node might be struggling to find a route because of the decentralization of the Lightning network. As the network becomes more decentralized, payments become harder to process simply because the native pathfinding algorithm sucks.

I can look into opening some direct channels with coinos.io wallet, maybe that can help.