You tried Hostal Cantábrico and they were full? How odd!! They have more than 100 rooms! What are the chances of that happening???!

You've already called Hostal Adriano ? And they too are full? Did they mention their NEWLY OPENED (JUST YESTERDAY!) Hostal Adria? - located just across the hall from Hostal Adriano. The building is well located too, not far from Puerta del Sol or Plaza Mayor. Hostal Adria doesn't have a website yet but one should be ready by the end of the week. It's BRAND NEW, new furniture and everything. I'd LOVE to get the first review of this place.

As for your question about online availability checkers, I don't trust them but suppose they're mostly reliable but most of those where you can check availability go through the HotelSearch.com reservation system.

Best of luck to you! Saludos, MadridMan