Okay, I can't believe I'm contributing to this noise, but ... I'm not sure I ever read where the OP said anything about going through an ISP. What happens if they're shuffling through a plethora of open wireless access points? The DHCP requests are going to get various private IP's that the AP's provide to the internal NAT'd boxes. If I put a biquad antenna at the focal point of an 18" DBS/DSS satellite dish the available AP's can greatly increase.
just a thought ...