You are misunderstanding the problem. Not every packet is a response and not every packet can be matched to some other packet such that "same network interface as they came in on" makes sense. What you want to do is select the gateway for a packet based on its source IP address.
This is called source-based routing or policy routing. You can do it with a simple
iptables rule, but the best way is to set up two routing tables, one for each public source address:
First, create two tables (Replace <NAME1> and <NAME2> with sensible names for your two providers, same with IP1, DEV1, and so on):
echo 200 <NAME1> >> /etc/iproute2/rt_tables
echo 201 <NAME2> >> /etc/iproute2/rt_tables
Add a gateway to each routing table (if needed):
ip route add <NET1> dev <DEV1> src <SRC1> table <NAME1>
ip route add <NET2> dev <DEV2> src <SRC2> table <NAME2>
Then a default route:
ip route add default via <IP1> table <NAME1>
ip route add default via <IP2> table <NAME2>
Then the rules to select the route table based on the source address:
ip rule add from <IP1> table <NAME1>
ip rule add from <IP2> table <NAME2>
See Routing for multiple uplinks/providers for more details.