The first thing to address in the words of Jakob Nielsen and one of his ten Heuristic User Interface Principles
Even better than good error messages is a careful design which prevents a problem from occurring in the first place. Either eliminate error-prone conditions or check for them and present users with a confirmation option before they commit to the action.
If form elements are placed in the right layout/structure some of your validation issues will solve themselves. Some overall positioning and layout guidance I have been given/used in web applications is too:
Arrange cross-dependent inputs in such a way users would not logically attempt to jump to the last input first. "One must start something before they can end it." so logically have start date before end date.
Place any cross-dependent input in tab order of each other. This way
users are one "tab" key away from the next dependent field(s).
Make inputs labels/instructions as simple as possible.
Segment large amounts of cross-dependent inputs into smaller logical sections and place in a progress/wizard workflow if applicable.
As stated these are basic guidelines. Since its not possilbe to prevent users from every making errors validation logic is still going to need to be added to some level. In these cases focus on putting only the simplest set of validation in place at the beginning of an application and slowly increase the validation requirements as a user moves through the application for cross dependent inputs.
Example:
If your validation engine normally validates on blur, change it so the first inputs validation rules are much more lenient. I.E allow Start Date to be either no value/ has a value that is formatted correctly; and not in the past (if that is a requirement in the business logic). Then force the End Date validation to be much more strict to ensure both fields contain logical date values or nothing at all (if allowed based on business logic).