Filtering Matrix through field value and multiple relations
You're right, this isn't possible with setting relatedTo parameters. But you can pass your ElementCriteriaModel (with all other parameters set) to the buildElementsQuery method, to prepare a DbCommand object. You can now modify the query as you need (→ Craft documentation for Database Queries).

Use join to bring in the "matrixblocks" table and also your Matrix field's content table "matrixcontent_mymatrixfield". Then add the min. and max age conditions with andWhere.

private function addAgeCriteria(ElementCriteriaModel $criteria, $age)
{
    $query = craft()-&gt;elements-&gt;buildElementsQuery($criteria);

    $params = array(
        ':age' =&gt; $age
    );

    $conditions = array('and',
        'matrixcontent_mymatrixfield.field_linkedTo_minimumAge &lt;= :age',
        'matrixcontent_mymatrixfield.field_linkedTo_maximumAge &gt;= :age'
    ),

    $query-&gt;andWhere($conditions, $params);

    $query-&gt;join('matrixblocks matrixblocks', 'matrixblocks.ownerId = entries.id');
    $query-&gt;join('matrixcontent_mymatrixfield matrixcontent_mymatrixfield', 'matrixcontent_mymatrixfield.elementId = matrixblocks.id');

    $results = $query-&gt;queryAll();

    return EntryModel::populateModels($results);
}