They do not use visited URLs. While Firefox separates its location and search bars, this seems to me more of a design choice than a privacy one. I could be wrong! - but then again, the much bigger privacy risk is using Google in the first place, and if you switch to a different search engine then Google stops receiving autocomplete too.
You are wrong, they specifically say that this is a privacy measure to anyone who whines that they want a "superbar" like Chrome's.
Using Google is a privacy risk but at least you can control it with Firefox, when typing URLs that need privacy. Who the hell can verify what Google (and the NSA listening to their pipes) does with your visited URLs? If you use another search engine, Google can see that, and it's one more piece of information.
By default Chrome sends the text you type in the location bar to Google. I am not sure but they may also use visited urls to source the crawler.