While I'm not 100% up on the reasoning behind why it doesn't work as expected, there seems to be a very large conflict with the mDNS service (Avahi in Linux, Bonjour/Zeroconf in Mac/Windows) and Windows networks that use .local as the internal routing name for domains. What seems to happen is that when pinging server01, it's skipping over using mDNS for resolution and then appending the search domain (foo.local) to the request, successfully querying the DNS server for server01.foo.local. However, when using mDNS (which uses .local as the default machine name extension), when you try to ping server01.foo.local, it's actually broadcasting over mDNS looking for a machine with the name of "server01.foo"; when it fails, it doesn't move on to straight-up DNS for whatever reason. A large workaround to this is not naming your domain .local, which probably goes against most Windows admins' training for domain structuring. That being said:
If mDNS is of no consequence in your network (as is common in the enterprise, which tends to run dedicated DNS servers versus the home network, where mDNS is sometimes used), then changing the search order is the easiest workaround.
This can be found in /etc/nsswitch.conf. The section for hosts will list the order, which for Fedora 16 default is:
hosts: files mdns4_minimal [NOTFOUND=return] dns myhostname
If you change that to:
hosts: files dns mdns4_minimal [NOTFOUND=return] myhostname
where you're moving dns ahead in the search order, that should fix things for now. Alternatively, if you know you're not going to need mDNS at all, just remove the "mdns4_minimal [NOTFOUND=return]" portion.
Looking at this bug on Red Hat's tracker, it seems that this is a long-standing problem with no apparent fix at the moment. Though, if someone can provide more insight as to why this happens this way, it'd be appreciated.