There seemed to be many ways to do this, but all adhoc and no complete solutions. So I present the following. Example in bottom screenshot.
In your Nintex Form (classic).
3. (Optional) - Remove the Recurrence label and control from the form. If you don't, it will be hidden anyway.
You can also update the Error Text value on the second line if you wish to change the default.
Note: This solution is working on the assumption that your region date format is dd/MM/yyyy. If you need to use MM/dd/yyyy, please un-comment Line 29 (remove leading 2 forward slashes). Then comment Lines 25 & 26 (add 2 forward slashes to the start of each line).
6. Save and Publish your form.
If there is an existing booking an error is displayed and the Save buttons are disabled. When a period is specified that doesn't already have a booking, the Save buttons are enabled again and the error is no longer displayed.
I have also expanded the solution to work with an additional column e.g. a resource like a Hot Desk. So if you have multiple Hot Desks or resources. It would validate that, that resource isn't booked already.
Enjoy! This one took a while to put together.