If you've been watching over the past few months they've slowly been reducing the power of their search. Probably to limit server load.
It will try to do it's damn best for you not to search all categories, all over the world.
If you search all categories for example, you cannot sort by price + P&P
