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,

Mike