Yes, you should be able to use destination nat in both ISP. What are the failure symptoms?
Are both ISP in the same routing domain or virtual router?
If so, you might also need to use source nat on the inbound traffic to be sure the reply traffic goes back out the same isp if your default route points to the other isp.