Search to the Right (myxiplx's thoughts)
One problem with having search on the right is that I think it works really well on the left with the default view. This mockup keeps search right at the top, in the most prominent possible position to encourage people to use it initially. The most recent programs and documents can filter in place as you type, and you can also filter running windows live too.
Now, I'm not too keen on the idea of the more / less button moving, so that's a detail that would need a bit more thought. But I really do like the search moving - it emphasizes that you're searching the list of programs, not the category.
Note: As before, download these as a bunch if you want to flick through and get the animation effect.
Idea 1 - default overlay, searching in place
Idea 2 - search moves as you click more
PS. You may have noted that I'm still using a vertical list of programs here. That's because I personally think it's nicer to work with than a group:
With a vertical list, you have one motion to carry out with the mouse. With a grid, I strongly suspect that people will be circling the mouse around a few times before finally finding the program they want to launch.