Well, turns out there IS an official app to unbind the socblue A860. It's only mentioned in the Chinese version of their website (http://www.socblue.com/_d275534130.htm) and in some forum posts by their support staff.
It's the one I mentioned in the original post, it's still there. The link looks dead because there's no direct download to an Android app, it's and iOS download repository and the app seems to exist only for iphone/ipad.
So for reference, if you need to unbind a socblue A860 and have lost the original phone is was bind to. You have to:
* Have a jailbroken iphone/ipad that has Cydia (http://cydia.saurik.com/) installed on it
* Make sure the normal socblue app is not installed
* Add "http://apt.fise.com.cn/db" as a source to Cydia
* Install the socblue app from that source
* Use the app to Search, connect and unbind your socblue A860
Using this official app I've been able to get the device back to work with a new phone.
Lets hope the message does not get deleted this time as it contradicts the official response.