hotels do not have rooms available all the time. our rooms have not been available in europe on a number of occasions(at least 10).first, try to get in early on the cheap. no deal, reserve an inexpensive hotel with your arrival time.
in london, we rented a flat in center point, and they would not crack on the arrival time. we usually arrived at lhr when they opened the runways, and were in center london by 8am or so. we stay at the st giles, for about ₤70, list, shop for a deal. you tell them, and your arrival time, and departure times, and ask for a special rate. although they supposedly speak english, don't bet on it.