Es muy facil ordenalo por tu "pai_id" y listo
Código PHP:
<select name="xx" id="xx"><option value="<?php $rs['pai_id'];?>">Select a country </option>
<?php
$listarcom="select pai_nom,pai_id from pais order by pai_id asc";
$ejecutar_listarcom = mssql_query($listarcom,$con);
while($rs = mssql_fetch_array($ejecutar_listarcom,$base)){
echo "<option value='$rs[pai_id]'>$rs[pai_nom]</option>";
$rx=$rs['pai_id'];
}
?>
</select>
Avisame si algo está mal...
Saludos.