Connection issue: outlook and Exchange

I have Windows NT server with Exchange and configured for DHCP, WINS and DNS. All the users computers and server are on same network of 192.168.1.0. Before my ISP was hosting MX records in their DNS server but now they want me to do it on my Exchange box. The problem is when user try to open outlook it times out and than they have to click retry to connect to their mailbox in exchange but it takes up to 5 minutes to connect first time. DSL router, which is configured as a Gateway with 192.168.1.254 ip.