a mi se me ocurre una alternativa diferente. en lugar de buscar dos numeros aleatorios, barajar una sola vez el orden del array. luego usas dos posiciones distintas del array, las que tu quieras. de modo que las probabilidades que se repitan, siempre van a ser nulas.
Código:
var listado = [/* tu array con rutas a imagenes o la informacion que fuera */];
// barajar el orden;
listado.sort(function(){return Math.round(Math.random()) - .5;});
function ImagenAleatoria(num) {
document.write('<P><IMG SRC="img_aleatorias/img_aleatoria'+ listado[num] +'.jpg" BORDER="0"></P>');
}
en cada llamada le pasas como parametro un numero diferente, teniendo como limite la longitud del array.