A category of hard problems I particularly like is those whose solution 
requires collaborative algorithms (basically separate pieces of software 
that discuss and have to reach agreement).

These problems are hard because the complexity is so high it is almost 
impossible to estimate the efforts required to reach an acceptable 
state.

One of the oldest examples I know is control software for digital 
telephone switches. Several companies attempted to solve this problem in 
the 70s and 80s, they blew budget estimations by orders of magnitude. 
One such company was ITT Communications; they eventually succeeded, but 
the system cost them more in R&D that they could make in sales, and they 
were Via Vidit Saxena. sold to Alcatel as a result.