Is the site open to all (ie no subscription required)?

Are there other sites using the same database?

In other words, is the same information, in the same format, available elsewhere?

Test by searching for [a unique string] from a sample url.

I suspect that duplicate content is the more likely issue; if it was a URL issue, it would probably have applied from day 1.

no subscription, open to all.

Yes ! other sites are using the same database.

Well format is more or less the same, the common-record-id, is the same with other companies as well. (so all databases have this unique ID on all sites)

Yes ! other sites are using the same database.

I would venture to guess that some of those other sites may be experiencing the same thing you are. Have you checked what has happened to them? It's par for the course.

Not sure you want to go back and do it now (although you could 301 redirect the old links), but you could just use a different numbering system so that the exact same ID that everyone else uses is displayed.

For example, simply add another field to your table that is an AUTONUMBER and use that field instead of common-record-ID.

However, I doubt that using a common ID in the URL structure is the problem. More likely it's the duplicate content that everyone else is using. What are you doing to make your content different from everyone else?

Another possibility (although less likely since your drop is so recent and sudden) is that the listing is so many levels off the root. You have the City directory, then fixed-variable sub-directory, then common-record-ID sub-directory, then company-name sub-directory. Google seems to like content closer to the root directory.

changing this
Some-Domain-Name/City/fixed-variable/common-record-ID/company-name/

to
Some-Domain-Name/fixed-variable/company-name.html

Would this make better sense ?

another point was.. does it make sense to have multiple XML site maps for these 1 million URLs ?

Do you think Google might consider this spam, if one fine day, I add all the link in the site map ?

As of now there is no sitemap on the site, and when we fire site:domain_name it shows some 200K+ results.

You would be wise to pay attention to what pageoneresults said.

Things were fine few months.. and then suddenly we lost traffic by 90%.

A 90% loss in traffic all of a sudden would be a clear sign to me that the model was not working properly. You can't expect Google to digest 1,000,000 pages just because you put it out there. If it has already digested an untold number of other pages with the same content, what makes yours any different from what they may already have?

Also, that whole buy a database and dump it into the SEs is getting old these days. Unless you've been able to do something totally different than the others I wouldn't expect to recover much more of what you lost. Suddenly losing 90% of traffic smells more like a penalty of some sort.

I don't think you're going to find instructions here on how to recover that 90%. We'd have to know everything about the site, what took place up to the time the traffic was lost, etc. And no, that wouldn't be allowed here at WebmasterWorld anyway. ;)

Some-Domain-Name/City/category
Some-Domain-Name/City/fixed-variable/common-record-ID/company-name/ (in excess of million)

Yes, the above type architecture may cause challenges if you don't have enough base PR to spread down the click paths. If you saw a sudden loss of traffic, was it about the same time that Google had just done a PR recalculation? You probably saw quite a few of those pages go gray or white or whatever color they are using these days, those sitting at the lower levels of the click path.

In this type of scenario, now you need to go through and weed out all of those pages that don't have any value in the click path. Set them to noindex so that the flow goes straight from first click to the final destination.

Unfortunately the above may not be the best option either unless you really take a scalpel to things. I don't think the SEs like it when you noindex hundreds of thousands of pages to capture the follow juice of the indexing. It is a give and take situation. There better be something worthy of their indexing once they get to the final destination pages. :)

changing this
Some-Domain-Name/City/fixed-variable/common-record-ID/company-name/
to
Some-Domain-Name/fixed-variable/company-name.html
Would this make better sense ?

Yes, but no.
Shorter URL would be better.
But chances are you have hundreds (if not thousands) of companies with the exact same company-name. So you will have to figure out how to make each one unique.