I don't like either of them because they look like multiple numbers could be assigned to multiple persons which is obviously wrong.

You can get only one result for a search because you are not searching with wildcards so consider this. A person can have multiple numbers so for a person you can have a single hit. If you search for an exact number you'll also get a single hit. This can be made clear by naming the method appropriately: `FindExact`. Later you can add another one that can search with wildcards (patterns).

    class Phonebook
    {
        private readonly Dictionary<string, List<string>> _entries = 
            new Dictionary<string, List<string>>();
    
        public void Add(string person, string number)
        {
            List<string> numbers;
            if (_entries.TryGetValue(person, out numbers))
            {
                numbers.Add(number);
            }
            else
            {
                _entries[person] = new List<string> { number };
            }
        }
    
        public KeyValuePair<string, List<string>> FindExact(string personOrNumber)
        {
            List<string> numbers;
            return
                _entries.TryGetValue(personOrNumber, out numbers)
                ? new KeyValuePair<string, List<string>>(personOrNumber, numbers)
                : _entries.FirstOrDefault(x => x.Value.Contains(personOrNumber));
        }
    }

Currently searching for a persons would be faster because it is a key in the dictionary. You could add another dictionary that maps numbers to persons and make the number search as fast as person search by looking at the key instead of searching all values:

    private readonly Dictionary<NUMBER, PERSON> _numberPerson...

---

In your second solution you don't need a dictionary at all because use don't use it like it should be used. You loop twice over it to find either value. In this case you can also use a list.

If you want to use a dictionary then use it appropriately otherwise it doesn't make any sense.

Use two dictionaries to make the exact search even faster but don't loop twice over it.

You can also replace both queries with a single one:

    var query = 
        from x in myPhonebook
        where x.Key == input || x.Value == input
        select x;

Even better like so:

    var result = myPhonebook.FirstOrDefault(x => x.Key == input || x.Value == input);