Are you making the "traditional" ripened style of mozzarella, or the quick citric acid version? Presumably the cultured one would last longer.
I've been experimenting with this recently, as I would prefer to keep them in a weak brine than wrapped in plastic, but was having the same problem with them going soggy after 4 or 5 days. So my theory was that if I over-knead to make them hard & rubbery to start with, then they will soften up to an ideal texture after a few days (whereas if I make them a good texture initially, they end up getting too soft when stored in brine). Early days yet, but it seems to be working.