Sorry, been a little too busy to sit down and consider your options but here is a shot at it.

I might have to pull one of my routers out and set it up in a lab for some testing but you can give it a try as is.

Code:
!interface FastEthernet0/1
 ip address DHCP
 ip nat inside 
!

ip nat inside source route-map ISP1 interface FastEthernet0/0 overload
ip nat inside source route-map ISP2 interface FastEthernet0/1 overload
!
route-map ISP2 permit 10 
 match ip address 20 
 match interface FastEthernet0/1

! 
route-map ISP1 permit 10 
 match ip address 10 
 match interface FastEthernet0/0 
!
access-list 10 deny tcp any host FastEthernet0/0 eq (insert IM Ports)
access-list 10 deny tcp any host FastEthernet0/0 eq (insert IM Ports)
access-list 10 permit ip any any
 
!
access-list 20 permit permit tcp any host FastEthernet0/1 eq (insert IM Ports)
access-list 20 permit permit tcp any host FastEthernet0/1 eq (insert IM Ports)
!