DHCPOFFER NACKed upon first REQUEST

[Daniele Albrizio]

Some clients (quasi 40 out of 2000) are being NACKed just after offering 
a lease like this:

Mar 17 14:27:48 luna dhcpd: DHCPDISCOVER from 74:f0:6d:0c:6e:6f ...
Mar 17 14:27:48 luna dhcpd: DHCPOFFER on 140.105.105.75 to ...
Mar 17 14:27:48 luna dhcpd: DHCPREQUEST for 140.105.105.75 ...: lease 
140.105.105.75 unavailable.
Mar 17 14:27:48 luna dhcpd: DHCPNAK on 140.105.105.75...

This happens not always for the same client.

The shared network segment needs to give out more than 2k leases during 
rush hours.

Syslog and packet dumps are available here:

http://pastebin.com/YVd032Pq

Note that the same client after a while (18 mins) successfulli gets the 
lease and uses it for 10 minutes.

Meaningful server configuration on both servers (failover configuration) 
is here:

http://pastebin.com/DjibSBCY

All gateways are configured on the same router relay interface.

Last lease for that ip on secondary failover is:

lease 140.105.105.75 {
   starts 1 2014/03/17 08:44:13;
   ends 1 2014/03/17 08:46:13;
   tstp 1 2014/03/17 08:46:13;
   tsfp 1 2014/03/17 08:46:13;
   atsfp 1 2014/03/17 08:46:13;
   binding state free;
   hardware ethernet 8c:be:be:71:xx:xx;
}

On primary failover is:

lease 140.105.105.75 {
   starts 1 2014/03/17 08:44:13;
   ends 1 2014/03/17 08:46:13;
   tstp 1 2014/03/17 08:46:13;
   tsfp 1 2014/03/17 08:46:13;
   atsfp 1 2014/03/17 08:46:13;
   cltt 1 2014/03/17 08:44:13;
   binding state free;
   hardware ethernet 8c:be:be:71:xx:xx;
   client-hostname "android-8c3c88a431f45c24";
   on expiry {
     set clientIP =
        binary-to-ascii (10, 8, ".", leased-address) ;
     if exists agent.remote-id {
       set clientMAC =
          binary-to-ascii (16, 8, ":",
                            substring (option agent.remote-id, 2, 6)) ;
       execute ("/etc/adminscripts/dhcp/leasebacklog.sh", "expiry", 
clientIP, clientMAC, "", "");
     } else {
       execute ("/etc/adminscripts/dhcp/leasebacklog.sh", "expiry", 
clientIP, "", "", "");
     }
   }
   on release {
     set clientIP =
        binary-to-ascii (10, 8, ".", leased-address) ;
     set clientMAC =
        binary-to-ascii (16, 8, ":",
                          substring (hardware, 1, 6)) ;
     execute ("/etc/adminscripts/dhcp/leasebacklog.sh", "release", 
clientIP, clientMAC, "", "");

No leases were present on both servers for the actual client mac address 
until successful transaction.

I'm bumping my head in a dead end. Every suggestion would be very 
appreciated. Thanks!

Daniele