Sorry I didn't get back sooner - other issues came up.
The Exchange users who are not on the WAN have DSL, cable modem,
wireless from various service providers.
Here's an interesting note -- it may not be an Exchange issue, but
rather an OS issue: I stopped all the Exchange services and restarted
them, but the issue remained. Rebooting the server completely
definitely fixes it.
Does that help?