In fact, I think it would actually be difficult to write a trading / matching engine that performed as slowly as mtgox. Seriously.
I think it's quite easy; store all orders in an unindexed table in MySQL and run a badly written SQL query to find the next match. I've seen enough awful code to suspect sheer incompetence way before suspecting malice, aka Hanlon/Heinlein's Razor...