You got a lemon E8400 like mine, it happens mate, it happens, and it does suck.
I can get mine stable at 3.8Ghz, but it requires 1.41v in CPU-z (1.43 vCore in BIOS). It currently sits at 3.75Ghz at 1.40v (CPU-z), the temperates are "fine" though, around 35ºC to 40ºC (depending on ambient room temperature) idle, and up to around 60ºC on load (during Prime95). But not only does it require 1.40v for a mere 750Mhz increase, it also needs +0.20v in both MCH and FSB voltages which is absolutely horrendous of a requirement for stability, but if I don't do it then it won't go beyond 10 minutes in Prime95 or Orthos at Priority 10, and I know that my memory is out of the equation since I've isolated it and tested under both stock and over-clocked speeds in both the Desktop and BIOS (Memtest) and it never gave me a single error.
So... yeah, it happens, the majority of E8400 owners reached good over-clocks, but there are a few batches out there that aren't even worth talking about. I bought mine way back in late 2007 when it was first released, in was the exact same week of its release in fact, and so I got a really sucky batch, while probably more than half of the E8400 owners out there got a good one. I once thought it was my motherboard's fault, but I found out that the same motherboard gave astounding results (many GA-X38-DQ6 and E8400 combos I read about after a mere Google search just made me realize that it was indeed my CPU that was the cause, it's one heck of a giant lemon).
And so, if you really want and especially if you really like to over-clock and you don't feel good enough with your E8400 then yes, I'd say go with a Q9550, or even a Q9650 if you can afford it. I myself am planning on going with either a Q9650 or i7 920 in about two or three months, but I don't think I'll over-clock anymore, I'm sick of bad results and it's probably my fault for buying new CPU's at their release and getting the first and bad batches, I should wait longer and wait for refreshes (such as the E0 stepping) to get better results, or I'm just one unlucky bastard since my first ever attempt at over-clocking with a Pentium 4 many years ago.