Tripadvisor is not useless--- some of the reviews can be helpful. However, I found that, with the single exception of the national holiday long weekend in October (the Easter weekend, which is March 31 in 2013, is also busy), I was almost always able to find non-albergue accommodation by just walking into the pueblo. From time to time, I would ask the innkeeper to call ahead for me to book a room at my next stop.
May is not a busy month, so I would suggest that, with the possible exception of your first night, you leave your booking until you are on the Camino, and only book a day at a time, as I described above. Even with a tight timetable (and I think that 26 days is going to be really difficult), you do not want to be boxed in and not have fleixiblity from the vagaries of weather, blisters and just wanting to stop and enjoy a day.