Seems like a solution would be to just have 4 weeks contracted leave which accrues. Then have an open policy on top of that which allows an employee to exceed 4 weeks per year.

Why on earth not? Accrue leave as normal, just allow the balance to go negative (or bottom out at zero). If it's positive when the employee leaves, pay them out.

Sure it is. You accrue four weeks annually. If you take three weeks, you've got a week saved up. If you take five, you have none saved up.