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).
1. Define "StartTime" as the Client ID JavaScript variable name for the Start Time control.
2. Define "EndTime" as the Client ID JavaScript variable name for the End Time control.
3. (Optional) - Remove the Recurrence label and control from the form. If you don't, it will be hidden anyway.
4. Copy and paste the JavaScript code from the attachment into your favorite Text Editor like Notepad++. Edit the first line and change "Calendar" to the Title of your SharePoint Calendar that your checking for double bookings.
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).
5. Copy and Paste the updated JavaScript into Custom JavaScript within Nintex Form Settings.
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.
Example:
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.