In reply to 1poundSOCKS:
The company (Slo pony) has changed its name to Asia Outdoors - just google 'Asia outdoors Cat Ba' and you'll find them. You can go DWS with them and the cost depends on how many people sign-up - although I have no ideas what the weather/water temp are like this time of the year - it may well be a bit cold for DWS??
I think their office may be your best bet in finding a partner for sports climbing (notice board / asking around). Also, when I was in Cat Ba, there was only one place that had bunk beds so if you stay there you might bump into another climber. Failing that, try to befriend the guys working for asia outdoors (go for a drink with them) and they might take you out on their 'off' days.
Hope this was useful