Lo que hace tu código es lo siguiente:
 
Si tenemos A1(1,2,3,4) y A2(2,4)
toma el valor de A1[0] (=1) y lo compara primero con el valor de A2[0], si es diferente (que lo es) hará un alert, luego lo comparara con A2[1] y como tambien es diferente tambien hace otro alert. Después coge el valor de A1[0] y lo compara con A2[0], como es igual no hará nada, pero luego lo compara con A2[1] y hará otro alert... no sé si me explico :D. 
Lo que tu quieres lo conseguirás con el siguiente código (creo :P) :  
 Código PHP:
    for (i=0; i<arr_valEli.length; i++)
{
      repetido= 0;
 
      for (j=0; j<arr_Pos.length; j++)
      {
            if (valorsel[arr_Pos[j]]==arr_valEli[i]) repetido= 1;
            // Que es valorsel[arr_Pos[j]]? No sería arr_Pos[j]?
      }
 
      if (!repetido)
      {
            alert('entro');
            valores_selAux= valores_selAux + arr_valEli[i] + '<BR>';
      }
}
 
// Hasta aquí obtendrás todos los valores del primer array que no están en el segundo
// Si quieres también los valores del segundo que no están en el primero copia lo siguiente
 
for (j=0; j<arr_Pos.length; j++)
{
      repetido= 0;
 
      for (i=0; i<arr_valEli.length; i++)
      {
            if (arr_valEli[i]==valorsel[arr_Pos[j]]) repetido= 1;
      }
 
      if (!repetido)
      {
            alert('entro');
            valores_selAux=valores_selAux + valorsel[arr_Pos[j]]+'<BR>';
      }
}