Thank you for reaching out.
I understand you are looking for a way to NAT traffic via Azure Express Route Private Peering using a public IP address to avoid IP overlap with your customer's network.
If I have understood your question correctly and depending on your requirements, I think you can try configuring a Site-to-Site VPN connection over ExpressRoute private peering as described here.
I am suggesting this approach because in this scenario you can utilize NAT on the Site-to-Site Azure VPN Gateway above which will help with the overlapping IP address issue. The advantage of such architecture will be that the communication will happen over a private network and no public IP will be required.
Based on your statement above
I was told that we can use Virtual Network appliance like Palo Alto but we wanted to see if this is something we can acheive by leveraging Azure native resources (Azure Firewall , NAT Gateway etc.)
Yes, you can use Azure Firewall to route your traffic over the internet, but the customer will also need to expose their services over a public IP for such communication to take place. You can use Azure Firewall Network and application rules to control such traffic flow.
Reference :
https://learn.microsoft.com/en-us/azure/firewall/tutorial-hybrid-ps
If this does not help answer your question, it would help if could provide a rough network diagram.
Hope this helps! Please let me know if you have any additional questions. Thank you!
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.