We have been in Plakias in May and did not experience any winds at all, that is not to say they may not blow. The worst of them are in July/August, which months we avoid, but as Gastronomis says, you are sure to have a great time, windy or not. May is a lovely time in Crete as the Spring flowers bloom and the air is fresher. I think I may be talking myself into a May visit!