[PEN-TEST] Any way to speed up mapping for penetration testing?

[Randy Molen <rpmolen () MAIL IT-PROTECT COM>]

Am currently working with a customer to map their network prior to
penetration/vulnerability testing using NMap.  Customer doesn't allow Ping
and wants 65000 ports tested.  Since we can't Ping, NMap takes a long time
to test a single host resulting in a very long testing period.  We've tried
setting a time-out value of 30 seconds but end up missing hosts with this
value.  Has anyone had an experience like this and if so, any
recommendations to efficiently map a network without Ping?

thanks