The reason you get 2 values is that, from the technical point of view, the address object has 2 fields for region.
This happens because not all the countries have support for regions.
For countries that don't support regions you get only the
region field. For does who have regions you get a value for both of them.
But in the
region_id field you get the increment id of the table
directory_country_region because that's how magento keeps a reference to the regions.
To get the region code you need an other query to the table mentioned above.
I see 2 options here.
Either create your own api method to which you pass the region id and get the details of the region or you modify the response for the address to include the region code.
I would go with the second option because it should be easier. you only need to add a new field in the wsdl for the address object and rewrite the model that retrieves the data for the order addresses.
Here is how you can add a new field in the wsdl. The example is for products but it works in the similar way for any other entity.
And you need to rewrite the method
Mage_Sales_Model_Order_Api::info, specially these lines
$result['shipping_address'] = $this->_getAttributes($order->getShippingAddress(), 'order_address');
$result['billing_address'] = $this->_getAttributes($order->getBillingAddress(), 'order_address');
and make them include the region code.
If you take the first approach, and create your own api method for the region this might help: How can I create a Custom SOAP/XML-RPC v1 & V2 Api in magento?
This is not an easy task. Good luck.