The search engine is good in that it allows you search (for most) *A flights (unlike US, UA for example), however you are correct that it doesn't display all available flights.

The easiest way around this (if you are a more seasoned flyer and already know possible route combinations) is to search each segment separately. For example, I am currently returning from a JFK-YVR trip booked as a *A award. When I searched JFK-YVR I got no available flights. But when I checked JFK-LAX/SFO and LAX/SFO-YVR I had several flights to choose from in Y, J and F.

Another example is a summer trip JFK-FCO, which also showed no availability on any airline, but a quick search of JFK-FRA/MUC and FRA/MUC-FCO yielded several possible choices on LH.

The annoying part about this is that you have to call to book the reward so they charge you $35 fee. I have told them many times of this flaw, but seems like the chances of them fixing it is slim to none.