Why can't C++ deduce T in a call to Foo<T>::Foo(T&&)?

The issue here is that, since the class is templated on T, in the constructor Foo(T&&) we are not performing type deduction; We always have an r-value reference. That is, the constructor for Foo actually looks like this:

Foo(int&&)

Foo(2) works because 2 is a prvalue.

Foo(x) does not because x is an lvalue that cannot bind to int&&. You could do std::move(x) to cast it to the appropriate type (demo)

Foo<int&>(x) works just fine because the constructor becomes Foo(int&) due to reference collapsing rules; initially it's Foo((int&)&&) which collapses to Foo(int&) per the standard.

In regards to your "redundant" deduction guide: Initially there is a default template deduction guide for the code that basically acts like a helper function like so:

template<typename T>
struct Foo {
    Foo(T&&) {}
};

template<typename T>
Foo<T> MakeFoo(std::add_rvalue_reference_t<T> value)
{
   return Foo<T>(std::move(value));
}

//... 
auto f = MakeFoo(x);

This is because the standard dictates that this (fictional) template method has the same template parameters as the class (Just T) followed by any template parameters as the constructor (none in this case; the constructor is not templated). Then, the types of the function parameters are the same as those in the constructor. In our case, after instantiating Foo<int>, the constructor looks like Foo(int&&), an rvalue-reference in other words. Hence the usage of add_rvalue_reference_t above.

Obviously this doesn't work.

When you added your "redundant" deduction guide:

template<typename T>
Foo(T&&) -> Foo<T>;

You allowed the compiler to distinguish that, despite any kind of reference attached to T in the constructor (int&, const int&, or int&& etc.), you intended the type inferred for the class to be without reference (just T). This is because we suddenly are performing type inference.

Now we generate another (fictional) helper function that looks like this:

template<class U>
Foo<U> MakeFoo(U&& u)
{
   return Foo<U>(std::forward<U>(u));
}

// ...
auto f = MakeFoo(x);

(Our calls to the constructor are redirected to the helper function for the purposes of class template argument deduction, so Foo(x) becomes MakeFoo(x)).

This allows U&& to become int& and T to become simply int

I think the confusion here arises because there is a specific exception for the synthesized deduction guides regarding forwarding references.

It is true that the candidate function for the purpose of class template argument deduction generated from the constructor and the one generated from the user-defined deduction guide look exactly the same, i.e.:

template<typename T>
auto f(T&&) -> Foo<T>;

but for the one generated from the constructor, T&& is a simple rvalue reference, while it is a forwarding reference in the user-defined case. This is specified by [temp.deduct.call]/3 of the C++17 standard (draft N4659, emphasize mine):

A forwarding reference is an rvalue reference to a cv-unqualified template parameter that does not represent a template parameter of a class template (during class template argument deduction ([over.match.class.deduct])).

Therefore the candidate synthesized from the class constructor will not deduce T as if from a forwarding reference (which could deduce T to be a lvalue reference, so that T&& is also a lvalue reference), but instead will only deduce T as non-reference, so that T&& is always an rvalue reference.