We describe a detailed experimental investigation of the phase transition for several different classes of satisfiability problems including random k-SAT, the constant probability model, and encodings of k-colourability and the independent set problem. We show that the constant probability model has been prematurely dismissed in favour of the random k-SAT model. We also show that for each of these problem class the conventional picture of easy-hard-easy behaviour is inadequate. In each of the problem classes, although median problem difficulty shows an easy-hard-easy pattern, there is also a region of very variable problem difficulty. Within this region, we have found problems orders of magnitude harder than those in the middle of the phase transition. These extraordinary problems can easily dominate the mean problem difficulty. We report experimental evidence which strongly suggests that this behaviour is due to a “constraint gap”, a region where the number of constraints on variables is minimal while simultaneously the depth of search required to solve problems is maximal. We also report results suggesting that better algorithms will be unable to eliminate this constraint gap and hence will continue to find very difficult problems in this region. Finally, we report an interesting correlation between these variable regions and a peak in the number of prime implicates. We predict that these extraordinarily hard problems will be of considerable use in analysing and comparing the performance of satisfiability algorithms.