So do you think a VSO is the best way to go?
I think it is one solution of a few out there, a three phase voltage stabiliser is another and automatic one at that as it appears your voltage balance is somewhat unpredictable.
Now let's be clear here, this is all beyond what we would consider DIY and one should really consider getting a professional out to site and explain what you have to us, even consider having your supply monitored and data logged could give a better idea of the size of the issue if one even exists, we are going on the word of the installer here and it could be he simply made an error in testing, poor contact, cheap measuring instrument or simply fobbing you off to avoid replacing it at his own cost.
I don't think you have a cheap solution unless you want to simply swap the 3ph water pump for a Single phase version but I am not a big fan of going down that road if 3ph is available, single phase pump have more complexity to design so more things can fail, lower available starting torque, shorter life span and less efficient than its 3ph counterpart but it may do the job at the end of the day so like I said, get someone out on site to advice you based on the installation itself and like we are trying to do here - basing it on a mix of electrical theory experience and a few assumptions which may miss something crucial to design and/or advice.
A VSD option is unlikely to be suitable for your pump if it is simply rewound as I suspect it will be sealed and thus selecting the winding arrangements won't be an option unless you request the company to configure it for your VSD 3ph 230v option, this however leaves you with a pump that you simply cannot swap like for like in the future to match the pipework etc as you have customised the pump for yourself, suitable alternatives may exist that are off the shelf though.
If you want to maintain the 3ph pump option it looks like an expensive solution whichever direction you take, you could invest in a single phase pump and even buy a spare for less cost, as you may have found out by now submersible pumps are not cheap to say the least so you going to have to think about what route to take here.