Não há algo como "superaquecimento do BIOS" - o que você está vendo é uma mensagem mal formulada dizendo que o BIOS desligou o sistema para evitar o superaquecimento da CPU.
De seus sintomas, o problema mais provável é o contato entre a CPU e o dissipador de calor ou um heatpipe quebrado. Para confirmar isso, você esperaria ver o ar frio ou quente, mas não o ar quente saindo da ventilação de escape, mesmo quando o ventilador estiver funcionando a toda velocidade.
Você precisará substituir a pasta térmica entre o processador e o dissipador de calor e, se isso não resolver, o próprio dissipador de calor. Se você disser que limpou a área do processador, presumo que você tenha conseguido desmontá-la, mas se não, aqui está um ponto de partida:
É possível encontrar facilmente mais guias:
link