Short answer - as detailed as they need to be for what you need to test (and no more)
Long answer:
In my experience, each time you expose users to prototypes (and then retest with them), the expectation is that the level of fidelity will increase. Of course, if you want to be able to analyse the results consistently, keeping the level of fidelity the same will be easier in some cases, and harder in other cases. It all depends on the expectation that you have set out with the client and the type of testing you want to do. Generally the closer you are to a release the more likely it will be that a high fidelity prototype will be the preferred option.
However, keep in mind that the only logical next step from a high-fidelity prototype is an actual working or interactive prototype, so if there is a long lead time between design and development then it makes sense to keep the level of fidelity as low as possible so as to manage expectations better.
Typically high fidelity prototypes are best suited to very fine design details that you want to test with users, and not as useful for things like workflow and content requirements because people get caught up or distracted with the density of design details (e.g. colours, icons, actual data, etc.).