Problemas intermitentes como esses são difíceis de diagnosticar, mas cheiram como um problema de hardware.
memtest86 + é uma boa ideia. Além disso, você está monitorando sua CPU e outras temperaturas da placa-mãe? Eu acredito que o superaquecimento pode causar falhas intermitentes como as que você está vendo. Quando a placa principal foi substituída, o dissipador de calor pode não ter sido reconectado bem à CPU (ou chipset). Uma coisa barata para tentar seria substituir a camada de interface térmica entre a CPU e o dissipador de calor.
Se isso não funcionar, provavelmente você terá que começar a trocar componentes de hardware para excluir cada um deles. Comece com a placa de vídeo, se você tiver um sobressalente, mas parece que você pode ter falhas em vários sistemas, o que sugere uma placa-mãe ruim. Desculpe.