Wow. I think the UK's on the worse end of Europe, and here the statutory minimum is 28 days (pro-rated for part time employees) including bank holidays if given (i.e. you can not give bank holidays automatically, but the minimum's still 28). I would say 25+BHs (=33 in England & Wales, 34 in Scotland, 35 in NI) is pretty typical/unremarkable (from day 1) for white collar jobs at least, more is certainly available and some increase with service as you describe.

I'm surprised this doesn't come up in US/Europe salary discussions more (at least, I haven't seen it that I recall) - I've known and see it be a benefit (that people do use) to purchase extra holiday from their already higher than typical US starting point. Wouldn't make that much difference to the comparison if it was offered of course, but perhaps indicates Europeans would be choosier (or unhappier) with their hypothetical US job than they realise.