How can a method handle validation and entity creation without output parameters?

I have 3 simple classes. A Reference, a Parent, and a Child. The Child knows the Reference and Parent instances it's associated with. Here they are, initialization and other data/methods omitted:

class Reference
{
    public int ID { get; private set; }
}

class Parent
{
    public int ID { get; private set; }
}

class Child
{
    public int ID { get; private set; }
    public Reference Reference {get; private set; }
    public Parent Parent {get; private set; }
}

Here is a class that maintains collections of them:

class SetOfThings
{
    private List<Reference> _refs;
    private List<Parent> _parents;
    private List<Child> _children;

    // ...
    // initialization, etc
    // ...
}

It enforces constraints like

• cannot add a Child unless its Parent and Reference already exists
• cannot add a Child if another Child with the same Parent and Reference already exists

and so on. Currently, the AddChild method enforces the constraints with ArgumentExceptions and returns the new Child with a new unique ID:

class SetOfThings  // continued
{
    public AddChild(Reference ref, Parent parent)
    {
        if (!_refs.Contains(ref))
            throw new ArgumentException($"{ref} not yet known");
        if (_children.Any(c => c.Parent == parent && c.Reference == ref))
            throw new ArgumentException($"{ref} and {parent} already referenced by a child");

        int newID = MakeNewChildID();
        var newChild = new Child(newID, ref, parent);

        _children.Add(newChild);
        return newChild;
    }
}

All of my AddChild calls look like this:

Child newChild;
try
{
    newChild = AddChild(someReference, someParent);
}
catch (ArgumentException ex)
{
    UI.Alert(ex.Message);
    return;
}

// ...
// Trigger state change, update UI with new child, etc.
// ...

However, this feels like an abuse of the exception mechanism. It isn't really "exceptional" behavior when those ArgumentExceptions are thrown - it's just normal control flow. But I don't know how to avoid this:

• I could return a bool that indicates success/failure and use an output parameter to "return" the new child,

  bool AddChild(Reference r, Parent p, out Child c)
  

  but I don't get any indication of why a failure occurred, and output parameters sacrifice readability.

• I could return null to indicate a failure. The method signature wouldn't change, but I still don't know why failures occur. Moreover, a null reference probably shouldn't be expected behavior any more than exceptions should be.

• I could return a custom Notification object (or list thereof) that indicates failures with severity and message strings.

  Notification AddChild(Reference r, Parent p, out Child c)
  

  Lots of information, hooray! But I still need an output parameter. D'oh.

• I could return Notification, but construct the Child before passing it into AddChild, and expose the Child.ID property as a public settable so the SetOfThings can change it appropriately.

  var newChild = new Child(someRef, someParent);
  var notification = set.AddChild(newChild);
  if (/* notification is failure */)
      // change state, discard newChild, display message
  else
      // change state, use newChild, etc.
  

  But the public settable Child.ID property to make this work is confusing at best, and dangerous at worst.

Am I missing some obvious or common alternative? I'm not breaking new ground here, but I can't come up with a clear, readable way for a collection class to have creation and validation in the same method.