Unfortunately there are two different versions of Windows Live Search for Mobile. One US, with traffic data, and a UK version for the rest of the world, without. It doesn't matter which version you try to download, the site will download one standard installer no matter which country you select.
The first time the application runs, it checks the device location, and if you're not using a US phone it gives you the Rest of the World version. You can be in the US with a UK device and you won't be able to get the traffic data - so you could get stuck on an LA freeway without knowing how to escape the jam. Now Microsoft rarely makes two binaries where one will do, so I suspected that what we were seeing was something in the application configuration. I first used a mobile device registry inspector to see if the application was using the registry.
It wasn't. So it was time to pour through the Windows Mobile file system to see if there was anything there. There was. Sat right next to the application executable was a preferences.xml file. I copied it across to my desktop, and had a look through with an XML-aware text editor. The file contained some canned searches, details of most of my last few searches, as well as some slightly less obvious sections. In one, <R>, was the text GB. I changed it to US, and put the file back on the mobile device.
I reopened Windows Live Search. Bingo! The traffic option was now available, and I could see the state of the LA rush hour. At least I won't get stuck on that stretch of 110...