DHCP Server stops responding

We use a mix of 9x, NT and 2K clients that recieve an IP address from a SonicWall firewall. The problem is, almost weekly a client is refused an address with a “access denied” message on IP renewal. There are available addresses on the Sonicwall yet it refuses to issue an address to certain PCs, yet not always the same PCs. Any suggestions would be appreciated.