You don't even need to cycle MAC addresses; just send DHCPDECLINE messages for any address the server gives. DHCP requires that any address that elicits that response from a client MUST be marked unavailable, and provides no provision for it ever becoming available again.
Ignoring the client is the only automatic mechanism DHCP provides for countering this.
You have to remember that DHCP was written back when it was assumed that a competent systems administrator managed the server and could manually respond to running out of available addresses (which was considered a likely sign of misconfiguration), and didn't attempt to specify what to do in the case where it happens.
Not giving out an address and notifying the systems administrator is what the DHCP spec recommends in this case. In fact, section 2.2 claims "The allocation mechanism (the collection of DHCP servers) guarantees not to reallocate that address within the requested time" so any reclamation of IP address on the part of the server is technically in violation of RFC 2131.
I'm confused... are you therefore suggesting that this is how people like Linksys should handle this problem? I fully realize that the spec was written in another time, but I don't think tzs did: he is actually citing the spec as a reason why these leases should stay around. When you go to a coffee shop, the router does not and probably should not play a chime when it has run out of DHCP leases, causing the barista to go around the room finding laptops that have been setup incorrectly... the router should, and almost certainly does, just "figure something out", likely by reclaiming addresses.
There are sensible options available other than violating the leases.
For example, for a highly-used access point, it would make sense to give out only very short leases - say, 10 minutes. That'd support a churn of 25 clients per minute if you're giving out addresses from a /24 (and there's no reason why you couldn't use a smaller netmask, down to /8). It'd also be sensible to ignore a single MAC address once it had more than a handful of outstanding leases.
It doesn't help with a malicious client - but then neither does breaking leases. The malicious client can cause enough address flapping to make the network completely unuseable. You really can't protect a wifi network against a malicious client trying to DoS it - there's a myriad ways to do that apart from DHCP.
Ignoring the client is the only automatic mechanism DHCP provides for countering this.
You have to remember that DHCP was written back when it was assumed that a competent systems administrator managed the server and could manually respond to running out of available addresses (which was considered a likely sign of misconfiguration), and didn't attempt to specify what to do in the case where it happens.
Not giving out an address and notifying the systems administrator is what the DHCP spec recommends in this case. In fact, section 2.2 claims "The allocation mechanism (the collection of DHCP servers) guarantees not to reallocate that address within the requested time" so any reclamation of IP address on the part of the server is technically in violation of RFC 2131.