How long before PhD graduation should I start applying for post-doc positions?
It depends on the type of funding associated with the postdoc position: 

1) If the funding is already there and has a limited duration (for instance a one-year funding within a one-year research project), then indeed, the recruiter might not want to wait 10 months for you, since it would mean that an important part of the funding might be "wasted". 

2) If the funding is already there, but can be used later on (for instance a one-year funding within a five-year research project), then it could be possible to start only in 10 months. 

3) If there is no funding yet, and you need to get it yourself, then you have to start as early as possible, since it can take a long time for the whole process to finish. 

Note that case 3 is usually a process you started with a potential advisor, rather than answer to a particular announcement. In any case, it's always a good thing to informally contact potential advisors directly to see about the specificity of a particular position.