This does not seem obvious, but if the Report Service of your SQL Server is not running, the users of Microsoft CRM 4.0 cannot login via the Internet, although intranet login would still work.
Apparently the Internet Facing Deployment (IFD) of Microsoft CRM 4.0 depends on the Report Service of Microsoft SQL Server.
Also in Microsoft CRM's "Deployment Manager", select "Servers" in the left pane, you will see a list of servers in the right pane. Make sure that the server for the "Full Server" roll is enabled. Otherwise, IFD would not work, either.