Por mi parte yo te diría que eligieras un solo protocolo porque si tenes más de uno, la comunicación se degrada porque viajaría por todos los protocolos instalados.
¿Cual usar? Si tu red no va a tener acceso a internet o no vas a usar aplicaciones que se comuniquen por IP, podrías usar IPX/SPX o NetBeui.
El porqué no se comunican, puede ser por varios motivos... el cable crossover esté mal configurado o reventado, los pc's no tengan habilitado la opción de compartir archivos e impresoras, que no tengan el mismo grupo de trabajo, que las IPs no estén configuradas apropiadamente,etc.
Una cosa que si te puedo decir, es que al encender los equipos, debes darles un lapso de 1 minuto o más para que establescan la comunicación (eso lo he comprobado en 9x y Me).
Complemento esta respuesta con una consulta similar a la tuya
pc´s en red sin servidor !!