Does $Foo::foo->() not mean locate the sub in the package Foo?
No. $Foo::foo is a symbol living in the symbol table Foo, that's granted; but its contents must not neccessarily refer to package Foo. So the normal method lookup rules apply. Which means that AUTOLOAD in the package main is found first.
update: If the content of $Foo::foo is a sub reference in the Foo namespace, the Foo AUTOLOAD is found, eg
$Foo::foo = \&Foo::bar;
print $Foo::foo->(); # Foo
--shmem
_($_=" "x(1<<5)."?\n".q·/)Oo. G°\ /
/\_¯/(q /
---------------------------- \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}