Progress!
I submitted our complaint for the 3rd time (7 days after its original submission) and this time prefaced it with a statement that our next step would be to contact Ofcom.
This afternoon we received a phone call from Vodafone.
They have now decided that our sync speed is less than their guaranteed minimum (they've previously asserted that 58Mb/s was above the lower limit of what we could expect), but asked that we give their Tech team one last chance to resolve the problem (contacting us within 72 hours).
We will then receive a call back from this afternoon's gentleman on Monday to check on our satisfaction.
If we are not satisfied with the improvements (if any) by the Tech team then we can choose to leave (no penalty) if we want to.
Phew...
Watch this space