In reply to LankyPaddy:
As any Key Stage 2 Schoolkid will tell you, freezing doesn't KILL bacteria, it only slows their rate of reproduction down - when you taken them out of the freezer again, the survivors will carry on breeding - and bacteria can take YEARS to die out completely, even if you left them in the freezer.
Some kinda chemical solution as listed above sounds like the plan - maybe when you replace them, keep the new pair in the freezer from the outset - this will stop the new bacteria growing.
Also, since it sounds like you've got sumkinda toe jam problem, maybe socks and a trip to the chiropodist?
Will