You're right, mg: google throws up 7,500 'finds', and the few I looked at are of a very varied nature, from companies running back-packing tours to a learned paper on digital identity (don't ask - I didn't read much more than the title!)
This does seem to put the phrase into the category of 'Well Used' - possibly even into that of "Cliché"

The phrase doesn't appear in the Holy Bible, despite over 70 mentions of "strangers"
(http://godsview.com/ is a handy concordance, BTW)

Shakespeare is a bit better, with two possibles, but neither are exact.
The nearest is in King Henry 8th, Act 1 Sc 4, where "A noble troop of strangers" is announced to Cardinal Wolsey, who then refers to them six or eight lines later as "a noble company."
That's close, but probably not close enough.

The other Shakespearian reference is in All's Well that Ends Well, Act 4, Sc 1, where the Second Lord says, "He must think us some band of strangers ..." - this doesn't seem a very likely source.

Both of the above references are to "A company" rather than "The company ...", giving a rather different nuance to the word "Company."

I am left wondering if Simon and Garfunkel are actually the originators of the phrase - they are certainly very widely known and their lyrics are usually very original (not that that would debar them from using a cliché to make a particular point.)