Which one of these two statements is correct?
Our staff do ...
Our staff does ...
And is staffs ever correct?
In British English, one can say "our staff do", because they use plural verbal agreement to emphasize when an entity is made up of a group of people, whether this entity itself is marked as plural or not. This is also true of companies, bands, sports teams and other things which are commonly used in plural forms as well as singular forms. The verbs are usually plural for one band or many bands ("Many bands play at the festival" as well as "Radiohead are a band").
In American English, one says "our staff does", because in our grammar, we are not concerning ourselves with whether an entity is made up of many people or not. Since staff is singular, we treat it grammatically as singular. It is no different for us than a stick-staff in terms of grammar.
I disagree with Kosmonaut. In BrE, staff is used as both a singular and a plural for purposes of agreement, although plural is certainly more popular.
Here are some examples with singular (from the Oxford English Corpus):
Since the newspaper staff is inundated with these letters everyday, they have no choice but to publish at least some of them.
An intelligence staff is organic to the brigade and its subordinate battalions and squadron.
With regard to the question "And is staffs ever correct?" I note that a Google Books search for the phrase "merged their staffs" returns nine relevant unique matches, ranging from in year of publication from 1951 to 2014. Here are three typical examples. From Virginia Department of Welfare and Institutions, The Welfare Worker (1951):
The Winchester department of public welfare and the Frederick County department have merged their staffs, in a trial effort for one year. Mrs. Jane Gross, Superintendent of the Frederick County department, will serve as Superintendent of the combined staffs.
From Douglas Fox, The New Urban Politics: Cities and the Federal Government (1972) [combined snippets]:
While the NLC [National League of Cities] and the USCM [United States Conference of Mayors] often clashed throughout their histories on policy issues, with the NLC much less sympathetic to the demands of the larger urban areas, in recent years they have drawn much closer together. In the late 1960s they merged their staffs, and anyone writing to either organization will receive a response on a letterhead with the names of both organizations. At the same time, both groups continue to exist as autonomous organizations.
From Alan Kraut & Deborah Kraut, Covenant of Care: Newark Beth Israel and the Jewish Hospital in America (2006):
The ecumenical merger that consolidated the most voluntary hospitals into on medical care entity occurred in 1988 in Minneapolis, bringing together the Episcopal, Swedish, Lutheran, Catholic, and Jewish hospitals. The consolidation had begun in 1970 when Saint Barnabas Hospital merged with the Swedish Hospital to form the Metropolitan Medical Center (MMC). In 1988, MMC, which had absorbed other voluntary hospitals, merged with the Mount Sinai Medical Center to form the Metropolitan Mount Sinai Medical Center (MSMC). The hospitals merged their staffs, while their auxiliaries and foundations continued to operate separately. But these hospitals also had financial troubles that continued after the merger.
Google Books search results indicate indicate that in U.S. English "merged their staffs" is much more common than "merged their staff," which yields a single match. From Damien Broderick, The Spike: How Our Lives Are Being Transformed By Rapidly Advancing Technologies (2002):
On Earth, in Vinge's future world, large corporations with better computers merged their staff into linkages of thousands. Is this a horrible prospect of soul death, extermination of the self? One might expect such an interpretation from a libertarian like Vinge, but in fact he suggests otherwise: ...
This is consistent with my experience. When the publisher of the computer magazine I worked on decided to combine that magazine's staff with the staff of another computer magazine that the publisher owned, the process was referred to as "merging staffs." At any rate, that situation is one in which staffs as the plural of staff appears to be correct in the sense of "in common U.S. usage."