The separation standard was compromised between two international flights on crossing air routes. UAL862 was flying north-east along A579 at FL290 when the crew asked for clearance to climb to FL310 to avoid turbulence. This request was granted at 1255 and the aircraft climbed to the new level. Its calculated time at position RUSUM was 1312. `ANZ39 was flying north-west along A464 at FL310. Its calculated time at RUSUM was 1311. The controller did not realise the confliction until 1309 and she immediately issued a descent to UAL862 which was relayed through the International HF Net manned by Flight Service. The aircraft did not respond to SELCAL. At 1312 an instruction to climb to FL330 was issued to ANZ39 via the HF link. The crew of ANZ39 reported that they had another aircraft displayed on their TCAS 14 to 15 nm south-east and at the same level. The separation standard of 15 minutes was breached at 1256 when UAL862 climbed to FL310. The Sector 8 controller had no direct communications with aircraft under her control. All air traffic instructions were relayed through Flight Service International on HF. The controller had approximately 6 to 8 aircraft under control in the sector. For reasons not established, the crew of UAL862 did not answer SELCAL. The New Zealand Air Traffic Controllers were on strike and international aircraft were directed on non standard tracks. This added to the complexity of the operating position where lateral separation points had to be calculated for each situation. Both aircraft crews were aware of the other aircraft due to the TCAS fitment in each aircraft.