Free 411 for the mobile masses | News.blog | CNET News.com: "Unveiled Wednesday at the Demofall conference in Huntington Beach, Calif., Free411, which can be reached by calling 800-free-411, is an interesting utilization of a free service that requires users to bear with a bit of advertising before getting the goodies."
This may be worth trying out and having handy in speed dial on the cell phone for when the need arises. The last time I reviewed my cell phone bill, I noticed my wife had made some 411 calls for a hefty price. I suggested she call me on the free mobile to mobile minutes, and I could do a search over the wireless Internet connection. This option should work as well.
Also, maybe try out with Gizmo Project - I think they let you call 1-800 #'s.