36-bit (or larger) physical addresses are not needed for PAE. This allows software to use PAE without caring about the physical address size (and without needing to write completely different paging code for some CPUs - e.g. Intel Atom). It also means that certain features that are only supported by PAE (and long mode) can be used on CPUs that don't have a 36-bit (or larger) physical address bus (specifically, the "no execute" or "execute disable" feature).
It's important not to confuse virtual addresses (addresses used by software) and physical addresses (addresses used by the CPU, hardware, etc). PAE has no effect on virtual addresses and all virtual addresses are still only 32-bit. If you access something at a 32-bit (virtual) address, the CPU converts the 32-bit virtual address into a 36-bit physical address using lookup tables (page tables, page directories, and the page directory pointer table).