The first puzzle about unemployment when thought about from within the search-matching framework is that unemployment rates are highest among the least skilled and most homogeneous skills, i.e. among those worker/jobs with the easiest matches. It's hard to believe that it takes a year to match a construction worker to a job.
Closely related is the issue of how much uncertainty is holding back employment. The case for uncertainty is that hiring a worker is like exercising an option–once you hire, there are sunk costs of hiring (and potentially firing) that go beyond the wage such as administrative and training costs.
Note that you may not need a lot of uncertainty (i.e. you may not need regime uncertainty) to reduce hiring because you don't have to explain why firms aren't hiring only why they aren't hiring this day. Even if we assume, for example, that hiring would be profitable, all else equal, it doesn't take much uncertainty to make it worthwhile to delay hiring a little bit, to wait and see. It's precisely when sales are low and unemployment is high that firms don't mind waiting because uncertainty may resolve in due course and the workers aren't going away.
Ok, that's the positive case for uncertainty but the second puzzle is that uncertainty should matter most when hiring and firing costs are high and once again these costs are lowest for those workers with the greatest unemployment rates. It's one thing not to hire when you can't fire but when firing is easy what's the risk? Moreover, unemployment has increased more in the United States than in Europe even though hiring and firing costs are higher in Europe.
Search-matching models of unemployment have a lot to add but don't necessarily overthrow the importance of AD shocks, sticky wages and prices and other sources of unemployment.