The reason why your alter is called twice is because Drupal needs to build the form at least two times: one for the first time is delivered to the user and a second time when the submit is done. The second build is needed because Drupal needs to know the complete form that was delivered to the user (for validation and security reasons).
You have two approaches to solve this:
Form API
As other have answered modify the form API behavior to avoid that second call:
Detect the second call and do not call the webservice (checking $form_state['triggered_element']['#name'] as told): it's ok but take into account that if the form built in the second call is different form the first one you may have problems with Form API complaining about invalid user input,
Enable form cache ($form_state['cache'] = TRUE). This way Drupal saves the form when is built for the first time, so the second time during submit, form is fetched form DB.
Cache webservice results
A second call to the webservice is not a problem if you cache webservice data because you retrieve the results from the cache instead of call it again. I think this is the best option if the nature of the webservice data allows to cache it.
This way the problem is solved in the webservice area while the other solutions involves that other components solve the issue (your form API code solves the webservice problem). If there's another similar use case you will have to solve again the proble, but if you solve it using webservice caching the problem is solved for all use cases.
#ajax
element on your$form
to call the webservice and change it whenever the user sees the form?