The simple answer is that a "search space" is available for the UE to use. Let's define what that is.
Let's assume that the PCFICH defines the "Control Region" of the subframe as 1, 2, or 3 OFDM symbols. After accounting for the resource elements (RE) used by the Reference Symbols, PCFICH, and PHICH, the leftover reference symbols may be used in PDCCHs for UEs.
When reading about PDCCH messages, they will be described as being made up of units of "Control Channel Elements" or CCE. There are 72 bits per CCE, and since RE in the control region are modulated via Quadrature Phase Shift Keying (QPSK) (2 bits per symbol), 36 RE are needed to define 1 CCE. This mapping from RE to CCE is defined in 36.311, (and will also introduce the terminology of a Resource Element Group, REG, which is a little outside the scope of this discussion).
So when thinking about the control channel it is best thought of in units of CCEs. Clearly the number of CCEs will vary as a function of: PCFICH, PHICH, and overall system bandwidth. However at the end of the day, you can think of being able to create a list of them numbered from from 0 to Number of CCE -1.
Enter the so-called UE search space.
There is a table found in 36.213 ... a link to a copy is here ... http://www.sharetechnote.com/html/Handbook_LTE_PDCCH_Candidate.html
The important thing to remember is that LTE performs error control on PDCCH messages through the addition of parity, and not so much via power control. therefore, table 9.1.1-1 provides details about the search space as follows.
First there are 2 search spaces defined, a common search space and a UE specific search space. Which you choose depends on which Radio Network Temporary Identifier you are searching for. System Information or SI-RNTI, Paging or P-RNTI, Random Access or RA-RNTI are found in the common search space. A UE's Cell or C-RNTI or perhaps it's Semi-Persistent-Scheduling (SPS)-RNTI are found in the UE specific search space. A UE should know what to look for depending on what state it is in. From the nature of your question, let's assume it's looking for it's own C-RNTI and thus we'll be looking at the UE specific work space.
As you can see, from the table, the maximum number of search space candidates that a UE must search for each aggregation level is defined. For UE Specific, there are 6 possible candidates of length 1 CCE, 6 possible candidates of length 2 CCE, 2 possible candidates of length 4 CCE and 2 possible candidates of length 8 CCE. Recall from above that the different lengths are LTE's mechanism for error correction.
So this table just defines how many candidates are on the list. Assuming for a second you have the list itself, it would CCE indices at which you would start to try to decode the PDCCH information. Where the indices point to CCEs in the list from 0 to #CCEs-1. So when you get the list, you know how many CCEs you're supposed to use when you try to decode the bits.
As a quick aside, the method described has to account for the most general case that assumes the maximum number of CCEs. The number of CCEs can vary drastically with PCFICH, especially in large system bandwidths. In such a case, you have to know to ignore possible starting CCE values that fall off the "edge" of the list.
The actual starting values are derived from the RNTI value itself. This is in 36.212 or 36.213, I forget which.
In order to determine "success", a UE must convolutionally decode the requisite number of CCE bits assuming a particular number of DCI bits, where DCI is downlink Control information. If a message was indeed intended for the UE, The checksum of the result will match the RNTI the UE is looking for.
I agree it's quite a cumbersome process. Don't shoot the messenger!!
Hope that helps.