I had a similar issue, and found out it was caused by a conflict with another translate plug-in called Ultimate Translate (for WordPress MU). I deactivated the Translate plug-in and the XML Sitemap plug-in worked once again.
I’ve posted a question on the developer forum of the translate plug-in to see if they have any info on this and other issues I was having with that plug-in.
@peteinnes any update on your search? Have you tried either of the suggestions above (ie: webreserv or booking calendar)? I’m looking for something very similar to what you described…would appreciate any info on what you ended up doing.
UPDATE: I just looked at both webreserv and booking calendar. As you would expect, they’re both very calendar centric. I need something simpler – more like what you described above.
Again, any feedback on your findings would be appreciated.