I should add that connections can be made between firewalled clients. But it would require the aid of a non-firewalled host service.

This is how services like Skype could still be usable by firewalled users. So long as the Skype service is hosted on non-firewalled host, the service can help negotiate connection between users.