Should it be an issue if you submit every page to your site map which is generated by a script i.e. a script that's being used to search for holiday lets. - given then each page will have the same meta tags. At what point might Google penalize you for this?
The description meta tag needs to be relevant to the page content. You could generate it by associating a description with a category/search type, for example: if it's about holidays in Paris, "Find flights and hotels in Paris, best prices available and discounts offered where possible". It would be easy to write some PHP to place the destination name in a generic description like this (i.e. replace Paris with Goa, New York City, etc). That would be a bare minimum to make each entry to look more unique in search results. What you really need to consider is the pages that will be indexed by search engines and the ones humans will view. The ones that will be indexed are the ones to be concerned about in terms of their meta description. As for keyword meta tags, they are irrelevant and don't even bother including them.
Well, its not a problem... but it may affect your CTR. Description helps the user in choosing the relevant results from the search results. If you could work on your description, it would impact your CTR.
agree. don't use duplicate meta tags! write unique relevant meta tags for each page. Good description and title increase traffic and position in SERP.