As instructed by @washi this is the optimal solution:
Both options are possible, but a confirmation rule is preferable because it saves resources and is faster than running a workflow.
The dates are not compared inside the rule, but a special lookup is created that uses the two inputs as parameters in a filter StartDate <= par_EndDate AND EndDate >= par_StartDate. This way only the overlapping records are selected. This lookup is then used in the rule as a variable. The results can be used either in an if clause (count is higher than 0) or a for-each clause when the exception should be returned with a parameter for each found record.