In response to The Many Tentacles and Simon89. In my humble opinion, just because NATS didn't tell you to book accommodation it doesn't mean they are not responsible. I mean, in many cases it is taken for granted candidates have to book for some night/s at a hotel. Simple proof of it is how NATS brags on about how multicultural their selection process is and how they have workers from all around the world. Secondly, due to their negligence they have caused you an unnecessary expenditure, a tort.
Of course, I would write it in a polite way and just hope for the best. But I do think it would be just fair they were made responsible.