I think writing a letter is perfectly acceptable and not rude at all. I would also start having the kids ready prior to parents arrival. You know what time they come to collect so have them all suited up and shoes on ready to leave. Sit them in a row and do story time or sing songs if that helps keep them focused on you and not goofing off.

In your letter make it clear that they signed a contract with late policies and fees in it and although you haven't been enforcing that, that from Monday this will be applied on every occasion and then make sure you follow through. You say this has been going on for 3 months, well after the first time of no consequences for their lateness, you are in effect giving them permission to do it again, as really what incentive have they got to stick to the rules when you don't do anything about it and apply them. They are pulling a fast one on you because you are letting them. I would verbally announce what your letter says so they have to acknowledge the message and then the written letter as back up confirmation.