Validating New Record with Related Records

I have a custom validation that validates a record by looking at
related records. The problem is that until the record has been saved
it has no id, therefore the relationships are not established. At the
moment the validation works for updated records but not new ones.

Any idea on how to validate most efficiently in this circumstance?

Many thanks,