I got caught without a place to sleep in Merida on the VDLP on the Saturday night of Easter in 2006.
I spent 2 hours walking and stopping to ask for a room in every hostel and hotel I came across. I also looked into the hotels listed in my guidebook. No luck.
My solution was to taxi 17 kms up the Camino to Alucen, a small village with an albergue that was not full.
I also learned that you can ask in a bar if they know of anywhere to sleep. They sometimes have rooms upstairs.
Good Luck
David, Victoria, Canada