That will depend on the directory tools like Synup, Moz Local can tell you when they go up on certain sites.

If it's not a popular one there are a few different scenarios :

1. Do they give you a temporary page that is only visible to you and will go live after it's approved? You can check the HTTP header response fo it and if it returns 200 it's probably approved and live.
2. Do they give you a live URL that says it's pending verification? Scrape the page and use XPath to see id that bit of text changes.
3. etc

Give us some more info on it and perhaps we can help.

You can use some of the tools here to personalize content on your landing page, that said Google will try and rank you for the content it sees when they crawl the site. You can try and see what they see using The Fetch as Google tool from Search Console.

Targeting Monkey

its hard to say what might be causing it without looking at the site. My best guess would be to see if its being pulled form any old G+ Local pages or schema.org markup on the site.

It's most likely because some one would have put a DMCA takedown on that Google search result. jump in to your Google WebMasterTools account and you should see some notification from Google about it.

How important is it for a sitemap to include all individual urls for the paginated content. Assuming the rel next and prev tags are set up would it be ok to just have the page 1 in the sitemap ?

The way I see it.

Google does not have a problem with proper use of things like media queries. More info : https://developers.google.com/webmasters/smartphone-sites/details . They ONLY have problem with webmasters when the hidden text is only available to search engines for SERP manipulation.

Read more into the " The Vary HTTP header " bit in the link above and some info from Matt : http://www.youtube.com/watch?v=va6qtaiZRHg&feature=player_detailpage#t=219

404 are OK on your site just make sure you send the proper 404 header response for the 404 page ... Google does NOT index 404 pages ( as long as it sends the 404 header response ) , so you don't need to block them via robots.txt or meta robots.

Infact GWT warns you about these if they are able to crawl the so called 404 pages that doesn't send a 404 header response , so I think its a good idea NOT to noindex them you will get the warning if something is wrong.

Google will only index your 404 if you don't do that..they call it soft 404 : https://support.google.com/webmasters/answer/181708?hl=en

worth reading : http://moz.com/learn/seo/http-status-codes

Not trying to throw a spanner in the works, but have you considered top level country specific domains ?  .co.uk, .au, etc

In theory you can use subdirectories and  assign geo targeting  for that folder in Google Webmaster Tools. ( keep in mind this will only work for Google, you have to look at how the other search engines will handle this Bing, Yandex if you target Russia, Baidu for China, etc )