Dual NIC Win2008 routing problem when private NIC enabled

Have Win2008 Terminal Server. Works fine if only public NIC is enabled.

But you want to enable the private NIC as well. What happens? Boom, nobody can access the Terminal Server (via public NIC).

Have tried:

• Setting a persistent static route (didn't work)
• Giving the private NIC a higher metric (didn't work either)
• Setting "Consider Unidentified networks as private" in local security policy (Computer configration –>Windows Settings –>Security Settings –>select Network list manager policies)
• Enabling weakhostsend/receive mode on each interface, as follows: (didn't work either)

    netsh interface ipv4 set interface "Private NIC" weakhostsend=enabled store=persistent
    netsh interface ipv4 set interface "Private NIC" weakhostreceive=enabled store=persistent
    netsh interface ipv4 set interface "Public NIC" weakhostsend=enabled store=persistent
    netsh interface ipv4 set interface "Public NIC" weakhostreceive=enabled store=persistent

None of these worked.

route print output:

IPv4 Route Table
===========================================================================
Active Routes:
Network Destination        Netmask          Gateway       Interface  Metric
          0.0.0.0          0.0.0.0    111.222.333.1   111.222.333.99     21
        127.0.0.0        255.0.0.0         On-link         127.0.0.1    306
        127.0.0.1  255.255.255.255         On-link         127.0.0.1    306
  127.255.255.255  255.255.255.255         On-link         127.0.0.1    306
    192.168.244.0    255.255.255.0         On-link     192.168.244.1    502
    192.168.244.1  255.255.255.255         On-link     192.168.244.1    756
  192.168.244.255  255.255.255.255         On-link     192.168.244.1    756
    111.222.333.0    255.255.255.0         On-link    111.222.333.99    276
   111.222.333.99  255.255.255.255         On-link    111.222.333.99    276
  111.222.333.255  255.255.255.255         On-link    111.222.333.99    276
        224.0.0.0        240.0.0.0         On-link         127.0.0.1    306
        224.0.0.0        240.0.0.0         On-link    111.222.333.99    276
        224.0.0.0        240.0.0.0         On-link     192.168.244.1    756
  255.255.255.255  255.255.255.255         On-link         127.0.0.1    306
  255.255.255.255  255.255.255.255         On-link    111.222.333.99    276
  255.255.255.255  255.255.255.255         On-link     192.168.244.1    756
===========================================================================
Persistent Routes:
  Network Address          Netmask  Gateway Address  Metric
          0.0.0.0          0.0.0.0    111.222.333.1       1
    192.168.244.0    255.255.255.0    192.168.244.1       2
===========================================================================

Update: After the suggestion below, I checked the binding order and corrected it. This made it work — until the server was restarted.

After a reboot, nobody could connect again. The binding order is still correct, with Remote Access Connections followed by Public NIC followed by Private NIC.

The difference is, AFTER THE RESTART, the Persistent Routes order in route print above reversed itself. So it becomes:

Persistent Routes:
Network Address          Netmask  Gateway Address  Metric
192.168.244.0    255.255.255.0    192.168.244.1       2
0.0.0.0          0.0.0.0    111.222.333.1       1

Any ideas on how to get the previous Persistent Routes order to stick?