With some ISPs, they will issue a new IP if you change the router's (WAN) MAC address. Might be worth a try next time (crossing fingers you don't need it).
This is what I've always seen too. I've never seen a residential ISP that allocates static DHCP addresses, they typically allocate in days which is why many people can maintain a leased address for months on end. Once you go offline though, all bets are off. Every ISP can determine if the subscriber is disconnected and if they are, they're going to reallocate your address. To your point, once the MAC address is changed, they have to issue a new IP address because using the logic posted above, the other address is allocated to a different MAC.