What is a valid parent for get_terms()?

The only variable which can really have an effect on the result as you described, is taxonomy. If you have verified that there are terms with a parent of 1 and a parent of 5, and get_terms() only returns terms for terms with a parent of 1, it can only mean that term 1 and term 5 belongs to different taxonomies. get_terms() will only return results if the term data passed is associated with the passed taxonomy.

You need to remember, all terms, regardless of taxonomy, are stored in the wp_terms table. Relationships are stored in the wp_term_taxonomy table. This is where the term’s taxonomy and parent is saved.

Here is a small script which you can run on any page. This will print all the taxonomies and all terms associated with that taxonomy and also print the parent ID if the terms aren’t top level terms. You can use this to “debug” your issue

$taxonomies = get_taxonomies(); 
if ( $taxonomies ) {
    foreach ( $taxonomies as $taxonomy ) {
        $terms = get_terms( $taxonomy );
        if ( $terms ) {
            echo '<strong>' . strtoupper( $taxonomy ) . '</strong></br>';
            foreach ( $terms as $term ) {
                $parent_id = ( 0 != $term->parent ) ? ' and has a parent ID of ' . $term->parent : '';
                echo 'Term '. $term->name . ' ID ' . $term->term_id . ' belongs to the taxonomy '. $taxonomy . $parent_id . '</br>';
            }
        }
    }
}