DNS lookups fail with e.g. `ping`, but work with `host`
Why they made this change, I don't know, but it's driven me crazy for a while. 

I don't know why things work for host, but not ping, but I think it has to do with the nature of these two utilities. Ping is a simple (although very helpful) diagnostic utility for dropping packets on the wire that should get echoed back to you. The hostname lookup functionality is just a side effect of the job and handed off to the system's recursive resolver (I believe -- I haven't verified by checking linked libraries or anything of that sort). Host's main job is to do DNS name resolution, so it implements its own recursive resolver. 

Apple's recursive resolver is mDNSResponder. For some reason, the version of mDNSResponder in Lion needs the "-AlwaysAppendSearchDomains" command line option to behave as it did in Snow Leopard (at least).

Here's a quick way to fix it:

sudo sed -i .orig '/ProgramArguments/,/&lt;\/array&gt;/ {
s/\(&lt;string&gt;-launchd&lt;\/string&gt;\)/\1\
                &lt;string&gt;-AlwaysAppendSearchDomains&lt;\/string&gt;/
}' /System/Library/LaunchDaemons/com.apple.mDNSResponder.plist


(There should be two tab characters at the start of the second-to-last line above, but I couldn't figure out how to get this little editor to insert tabs, so I added 16 spaces. Either should work, but the tabs fit the spacing of the original file better.) 

This will add the "-AlwaysAppendSearchDomains" argument to the mDNSResponder startup plist file (and save a backup copy), but since this is controlled by launchd, that system needs to be told to restart mDNSResponder.

sudo launchctl unload -w /System/Library/LaunchDaemons/com.apple.mDNSResponder.plist
sudo launchctl load -w /System/Library/LaunchDaemons/com.apple.mDNSResponder.plist


Now, if you check your running mDNSResponder process, you should see it running with your new argument:

ps auxww | grep mDNSResponder


(Props to http://www.makingitscale.com/2011/fix-for-broken-search-domain-resolution-in-osx-lion.html and http://kavassalis.com/2011/07/wtf-bug-in-os-x-10-7/, where I found my answers to this problem.)