I believe 15 seconds is the default flood interval, and is an appropriate value. Was hoping you would find someone had entered an unnaturally long value in there, which would explain the symptom.
On your main board index, check the "It is currently Mon Oct 08, 2018 xx:xx..." display near the top of the page to make sure the date isn't in the past, which should be enough of an indication of whether the hosting server's time is correct. That display is based on the server's UTC time, adjusted according to the time zone set in your user control panel profile.
The test used on the contact form is essentially just "if CURRENT_TIME minus LAST_USER_EMAIL_TIME is smaller than the FLOOD_INTERVAL, then report the FLOOD_EMAIL_LIMIT error". Which suggests either there is a recent "last email time", or the math must be wrapping to negative values because the current time pre-dates the last email time.
So the system time on the server could be wrong now, which makes the legitimate "last email" times all appear to be in the future. Or maybe the server was running with a wrong system time previously; and even though the server time is correct now, the recorded "last email" times are in the future from when the server time was wrong.
If you're not aware of the hosting server's time having been wrong recently (or now), that seems to leave only the even less likely possibility that something is "constantly sending mail as these users" now, such that there is always a "recent email" within the flood interval when you attempt to test with the contact form.
Beyond that, I'm out of ideas, and updating to a current 3.2.x version and confirming that the issue remains is probably the next step.