That is the confusion that other users have as well, which is caused by the misunderstanding how this particular search works. You think it searches the given pattern, say "*", for the given work item type, but actually it does not. It searches the given pattern first, then filters the result set by the given work item type. Chances are, you have many work items of other types, and the desired work item type gets drown out by the other types. For example, let's say there are 300 Defect work items and 10 Task work items, you think that selecting "Task" and "*" will give you all the 10 Task work items - not so easy. It may return 99 Defect work items and 1 Task work item, and when you filter by Task, you get only one. Of course if it returns 100 Defect work items (the default cap), you will get no Task work items.

A more reliable way is to use the Search by Query option. First create a query with condition "type is Task" and a dynamic full text search filter, then when you choose this query in the dialog, you can type in "PA*" or "*" to do the full text search within the Task work items. You should get the expected result this way.

IIRC this was observed in version 5.0.x. The 6.0.x release seems to behave the way we expect it would.