Welcome to WebmasterWorld Guest from 126.96.36.199
Is it possible that if you place well organically there is a filter that keeps your listing from showing in Google Maps which is shown on Google.com above the organic results?
How To Get My Business To Show Up As A Map In Google SERPs
Maps at the top of Google's SERPs
Also, Google Maps has been going through some reorganization recently, and the tabbed "more info" results are being replaced by Place Pages [webmasterworld.com], which we've been discussing here in the Google Search forum. It's possible, if your client was once listed in Google Maps, that those listings have disappeared in the reorganization.
I recommend taking a look at the Place Pages of competing local sites and seeing what Google is featuring on those pages. Then make sure that your client has similar resources and references available on the web.