We tested an E8400 on this board as well and had the same problems starting from ~520 FSB. I compared your voltages and as far as I remember we were running similar values. I don't think we handled the board wrong considering the settings - it simply wouldn't do it I say.
Last day of cebit we put exactly the same chip on a DS4 and we had it booting 580x9 after just a few minutes.
2 Chips on that board showed the same behaviour and both run great on Gigabyte LN2 cooled - so I was very disappionted about that board.
Anyway I am not very happy with Asus boards at all as my experience with P5K3 was a pain as well (but this mainly because of the limitation to 1.7Vcore unmodded). Maybe I should take an "Asus-lesson" with you