Sachverhalt:
A.
A.a. Der Schweizerische Baumeisterverband (SBV), die GBI Gewerkschaft Bau & Industrie (heute: Unia) sowie die Gewerkschaft SYNA schlossen am 12. November 2002 einen Gesamtarbeitsvertrag für den flexiblen Altersrücktritt im Bauhauptgewerbe (GAV FAR), mit dessen Vollzug die Stiftung für den flexiblen Altersrücktritt im Bauhauptgewerbe (Stiftung FAR) betraut ist. Durch Beschluss des Bundesrates vom 5. Juni 2003 wurde der GAV FAR erstmals teilweise allgemeinverbindlich erklärt.
A.b. Die A._ AG war nicht Mitglied des SBV. Laut Handelsregister bezweckte sie u.a. die Ausführung von Freizeitanlagen, Unterbau-, Pflästerungs- und Belagsarbeiten sowie die Uebernahme von Gartengestaltungen. Insbesondere gestützt auf die Selbstdeklaration der Arbeitgeberin vom 3. März 2009 teilte die Stiftung FAR der A._ AG am 6. Januar 2010 mit, sie sei "seit 1. Januar 2003" dem GAV FAR unterstellt und somit FAR-beitragspflichtig. Auf das Einspracheschreiben vom 13. Januar 2010 hin kam die Stiftung FAR am 22. Januar 2010 auf ihren Entscheid zurück und verschob den Beginn der Unterstellung auf den 1. Januar 2008. Die A._ AG entrichtete die Beiträge ab diesem Datum.
Im Oktober 2012 ersuchte ein langjähriger Mitarbeiter der A._ AG um Leistungen der Stiftung FAR. Diese lehnte das Gesuch zunächst mangels genügender Beschäftigungsdauer in einem dem GAV FAR unterstellten Betrieb ab. Nach weiteren Abklärungen kam sie zum Schluss, dass die Arbeitgeberin auch für die Zeit vom 1. Juli 2003 bis 31. Dezember 2007 vom Geltungsbereich des GAV FAR erfasst werde (Schreiben vom 18. September und 6. November 2013). Die A._ AG stellte die entsprechenden Lohnsummenmeldungen der Stiftung FAR nicht zu.
B.
Mit Klage vom 27. Mai 2014 resp. Stellungnahme vom 8. April 2015 beantragte die Stiftung FAR, es sei festzustellen, dass die A._ AG seit dem 1. Juli 2003 vollumfänglich dem GAV FAR unterstehe. Sodann sei die A._ AG zu verpflichten, ihr für jeden Mitarbeiter, der unter den persönlichen Geltungsbereich des Bundesratsbeschlusses über die Allgemeinverbindlicherklärung des GAV FAR (AVE GAV FAR) fällt, Beiträge von 5,66 % der AHV-pflichtigen Lohnsumme vom 1. Januar bis 31. Dezember 2004 und von 5 % der AHV-pflichtigen Lohnsumme vom 1. Januar 2005 bis 31. Dezember 2007, zuzüglich Verzugszins von 5 % auf den jährlichen Beiträgen jeweils ab 1. Januar des Folgejahres, zu bezahlen.
Das Verwaltungsgericht des Kantons Bern beschränkte das Verfahren mit Verfügung vom 20. November 2014auf die Prüfung der von der A._ AG erhobenen Verjährungseinrede. Mit Entscheid vom 26. April 2016 wies es die Klage ab.
C.
Die Stiftung FAR beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, unter Aufhebung des Entscheids vom 26. April 2016 sei die A._ AG zu verpflichten, ihr für den Zeitraum vom 1. Januar 2004 bis 31. Dezember 2007 Beiträge von Fr. 39'616.-, nebst Zins zu 5 % auf Fr. 12'283.- ab 1. Januar 2005, auf Fr. 9'399.20 ab 1. Januar 2006, auf Fr. 9'311.- ab 1. Januar 2007, auf Fr. 8'622.40 ab 1. Januar 2008, zu bezahlen; eventualiter sei das kantonale Gericht anzuweisen, die Sache in der richtigen Besetzung des Spruchkörpers und unter Berücksichtigung der Untersuchungsmaxime neu zu beurteilen.
Die A._ AG schliesst auf Abweisung des Rechtsmittels, soweit darauf einzutreten sei. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Das Bundesgericht prüft die Zulässigkeit der bei ihm erhobenen Rechtsmittel grundsätzlich von Amtes wegen und mit freier Kognition (<ref-ruling> E. 1 S. 31). Prozessthema des bundesgerichtlichen Verfahrens kann nur sein, was (zulässigerweise) Gegenstand des angefochtenen kantonalen Entscheides bildete (<ref-law>; vgl. auch <ref-ruling> E. 1 S. 414; SVR 2015 BVG Nr. 55 S. 234, 9C_671/2014 E. 1).
1.2. Das kantonale Gericht hat ausdrücklich weder die umstrittene Unterstellung der Beschwerdegegnerin unter den GAV FAR noch die geltend gemachten Beitragsforderungen (samt Verzugszinsen) materiell beurteilt. Mit der Begründung, Letztere seien jedenfalls verjährt, hat es dennoch abschliessend mit Schluss auf Abweisung der Klage über den Anspruch auf die Beiträge für die Zeit vom 1. Januar 2004 bis 31. Dezember 2007 entschieden. Darauf zielt auch das Hauptbegehren der Beschwerdeführerin. Dieses ist somit - anders als die Beschwerdegegnerin anzunehmen scheint - zulässig. Die Frage, ob das Bundesgericht bei einer allfälligen Gutheissung der Beschwerde reformatorisch oder kassatorisch entscheidet (vgl. <ref-law>; vgl. auch MEYER/DORMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 12 und 15 zu <ref-law>), betrifft nicht die Eintretensvoraussetzungen.
2.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht (<ref-law>).
3.
3.1. Bei der Stiftung FAR handelt es sich um eine nicht registrierte (vgl. Art. 48 BVG), ausschliesslich in der freiwilligen beruflichen Vorsorge tätige Personalfürsorgestiftung im Sinne von Art. 89a (früher: 89 bis) ZGB (Urteil 9C_975/2012 vom 15. April 2013 E. 2.1, nicht publ. in: <ref-ruling>, aber in: SVR 2013 BVG Nr. 39 S. 168).
3.2.
3.2.1. Forderungen auf periodische Beiträge und Leistungen verjähren nach fünf Jahren. Die Art. 129-142 OR sind anwendbar (Art. 41 Abs. 2 BVG i.V.m. Art. 89a [früher: 89 bis] Abs. 6 Ziff. 5 ZGB). Die Verjährung beginnt mit der Fälligkeit der Forderung (<ref-law>).
Laut dem mit Bundesratsbeschluss vom 5. Juni 2003 über die Allgemeinverbindlicherklärung des GAV FAR (AVE GAV FAR [BBl 2003 4039]; durch Beschlüsse vom 8. August und 26. Oktober 2006, 1. November 2007, 6. Dezember 2012, 10. November 2015 und 14. Juni 2016 verlängert resp. angepasst [BBl 2006 6751, 8865; 2007 7881; 2012 9763; 2015 8307; 2016 5033]) allgemeinverbindlich erklärten Art. 9 Abs. 2 GAV FAR hat der Arbeitgeber vierteljährlich Akontozahlungen für die Beiträge abzuliefern, fällig 30 Tage nach der Rechnungsstellung, spätestens jedoch per Quartalsende. Seit dem Inkrafttreten der 1. BVG-Revision auf Anfang 2005 besteht zudem eine gesetzliche Fälligkeitsregel für Beitragsforderungen. Danach überweist der Arbeitgeber die beiderseitigen Beiträge bis spätestens zum Ende des ersten Monats nach dem Kalender- oder Versicherungsjahr, für das die Beiträge geschuldet sind, an die Vorsorgeeinrichtung (Art. 66 Abs. 4 BVG i.V.m. <ref-law>).
3.2.2. Grundsätzlich kann auch eine dem Gläubiger unbekannte Forderung fällig werden (<ref-ruling> E. 4.1 S. 78 mit Hinweisen). In Abweichung von dieser Regel erfolgt bei qualifizierter Meldepflichtverletzung im Sinne einer unentschuldbaren Unterlassung des Schuldners ein Aufschub der Fälligkeit der einzelnen periodischen Beitragsforderung bis zu dem Zeitpunkt, in welchem die Beitragsgläubigerin davon anrechenbare Kenntnis erlangt (<ref-ruling> E. 4.2 S. 79). Von einer solchen grobfahrlässigen Verletzung der sich unmittelbar aus einem allgemeinverbindlichen Vertrag mit Gesetzescharakter ergebenden Verpflichtung zur Anmeldung und Bezahlung von Beiträgen an die Stiftung FAR ist etwa dann auszugehen, wenn sich ein dem GAV FAR unterstellter Arbeitgeber nicht selber bei der Stiftung FAR anmeldet. Unter diesen Umständen beginnt die fünfjährige Verjährungsfrist erst mit der (zumut- resp. anrechenbaren) Kenntnis der Stiftung von ihrer Beitragsforderung gegenüber dem betroffenen Arbeitgeber zu laufen (<ref-ruling> E. 4.1 S. 39 mit Hinweisen).
4.
4.1. Eine Verjährung der umstrittenen Beitragsforderungen fällt nur dann in Betracht, wenn sie spätestens fünf Jahre vor Einleitung der Klage (vgl. <ref-law>), mithin am 27. Mai 2009 fällig wurden. Entscheidend ist somit, ob die Stiftung FAR bis zu diesem Zeitpunkt infolge einer qualifizierten Meldepflichtverletzung durch die Arbeitgeberin keine anrechenbare Kenntnis von ihren Forderungen hatte.
4.2. Die Vorinstanz hat erwogen, die Arbeitgeberin habe im Rahmen der Selbstdeklaration und im darauf folgenden Einspracheverfahren sämtliche notwendigen Angaben für die Beurteilung einer allfälligen Unterstellung unter den GAV FAR eingereicht. Die Stiftung FAR habe sie weder zur Einreichung weiterer Belege aufgefordert noch detailliertere Ausführungen verlangt. Eine qualifizierte Meldepflichtverletzung sei somit nicht ausgewiesen. Dass die Angaben zu Umsatz und Maschinenpark falsch gewesen seien, habe die Stiftung FAR weder stichhaltig begründet noch belegt. Der Arbeitgeberin könne kein rechtsmissbräuchliches Verhalten vorgeworfen werden, zumal es sich auch nach Einschätzung der Stiftung FAR um einen Grenzfall gehandelt habe. Daraus folge, dass die Beschwerdeführerin spätestens mit der Einreichung der Selbstdeklaration vom 3. März 2008 um die Grundlage der Forderung gewusst habe oder hätte wissen müssen. Die umstrittenen Beitragsforderungen seien demnach spätestens Ende März 2013 verjährt. Folglich hat sie das Klagebegehren Ziff. 2 als offensichtlich unbegründet abgewiesen.
Die Stiftung FAR macht im Wesentlichen geltend, ihre Unkenntnis des Umstandes, dass die Arbeitgeberin bereits vor dem 1. Januar 2008 dem GAV FAR unterstand, und damit der umstrittenen Forderungen sei einzig auf die falschen Angaben in der Selbstdeklaration vom 3. März 2009 und im Einspracheschreiben vom 13. Januar 2010 resp. auf die unterlassene Berichtigung ihrer falschen Einschätzung vom 22. Januar 2010 zurückzuführen. Darin erblickt sie eine qualifizierte Meldepflichtverletzung.
4.3. Zunächst ist festzustellen, dass die Selbstdeklarationsformulare A und B von der Stiftung FAR am 27. Februar 2009 versandt und am 3. März 2009 von der Beschwerdegegnerin retourniert wurden; das Formular A wurde - anders als das Formular B - offensichtlich irrtümlich mit dem 3. März 2008 datiert. Die entsprechende vorinstanzliche Sachverhaltsfeststellung (E. 4.2) ist in diesem Sinn zu korrigieren (E. 2). Somit kann der Beschwerdegegnerin spätestens seit dem 3. März 2009 nicht mehr vorgehalten werden, sich nicht selber bei der Stiftung FAR angemeldet zu haben (vgl. E. 3.2.2).
4.4.
4.4.1. Für die Frage nach der Verjährung ist nicht ausschlaggebend, ob die Angaben der Arbeitgeberin zum Umsatz und zum Maschinenpark unrichtig waren. Die Ausführungen der Beschwerdeführerin betreffend die diesbezügliche vorinstanzliche Sachverhaltsabklärung und -feststellung zielen ins Leere. Wesentlich ist vielmehr, wann die Stiftung FAR eine mögliche Unrichtigkeit der Angaben resp. die Beitragspflicht hätte erkennen können, was sich ohne weitere Sachverhaltsabklärung beantworten lässt.
4.4.2. Wohl ist die Arbeitgeberin aufgrund des allgemeinverbindlichen Vertrags mit Gesetzescharakter insbesondere zur Anmeldung und Bezahlung von Beiträgen an die Stiftung FAR verpflichtet (E. 3.2.2). Laut den allgemeinverbindlich erklärten Bestimmungen von Art. 23 Abs. 1-3 GAV FAR obliegt indessen der Stiftung FAR der Vollzug des GAV FAR, weshalb sie insbesondere berechtigt ist, die notwendigen Kontrollen gegenüber den Vertragsunterworfenen durchzuführen oder durchführen zu lassen (Art. 23 Abs. 1 und 2 GAV FAR). Den Kontrollinstanzen stehen zur Durchsetzung der Bestimmungen des GAV FAR zudem folgende Berechtigungen zu: Betriebskontrollen im Geltungsbereich des vorliegenden GAV, Lohnbuchkontrollen, Kontrolle der einzelnen Arbeitsverträge (Art. 23 Abs. 3 GAV FAR). In diesem Sinn trifft die Stiftung FAR eine "Abklärungspflicht" und die betroffenen Arbeitgeber eine "Mitwirkungspflicht".
4.4.3. Die Selbstdeklaration vom 3. März 2009, der Handelsresgisterauszug und die Firmenhomepage bildeten Grundlage für den Entscheid der Stiftung FAR vom 6. Januar 2010, die Beitragspflicht der Beschwerdegegnerin seit 1. Januar (recte: Juli; vgl. Art. 5 AVE GAV FAR) 2003 zu bejahen. Als weitere Indizien sprechen der Name der Arbeitgeberin und das von ihr verwendete Logo für eine Unterstellung. Auch wenn die Selbstdeklaration vom 3. März 2009 lediglich für die Jahre 2007-2009 Angaben über Mitarbeitende und Umsatz und auch sonst nur wenig Informationen über die Geschäftstätigkeit enthält, leuchtet nicht ein, wieso daraus auf ein rechtsmissbräuchliches Verhalten der Beschwerdegegnerin im Sinne einer qualifizierten Meldepflichtverletzung geschlossen werden müsste. Spätestens mit dem Erhalt der Selbstdeklaration verfügte die Stiftung FAR insgesamt über genügend Informationen, um die Beitragspflicht der konkreten Arbeitgeberin zumindest im Grundsatz zu kennen (so auch in <ref-ruling> E. 4.3 S. 40 f.; SVR 2012 BVG Nr. 19 S. 79, 9C_783/2011 E. 2.2). Es ist denn auch nicht ersichtlich und wird nicht geltend gemacht, dass die Stiftung FAR in Bezug auf die Zeit vor 2008 weitere Informationen (vergeblich) eingefordert oder Kontrollen gemäss Art. 23 Abs. 3 GAV FAR - woraus sich zudem die Höhe der (allfälligen) Beitragsforderungen hätte eruieren lassen - durchgeführt oder auch nur in Betracht gezogen haben soll (E. 4.4.2).
Nach dem Gesagten besteht kein Grund, die Fälligkeit der hier interessierenden (nicht materiell überprüften; E. 1.2) Forderungen, von deren Bestand die Stiftung FAR selber explizit im Entscheid vom 6. Januar 2010 ausging, über den 27. Mai 2009 hinaus aufzuschieben. Die Vorinstanz hat sie somit im Ergebnis zu Recht als verjährt betrachtet.
4.5. Auch das weiter von der Beschwerdeführerin gerügte Verhalten der Arbeitgeberin ist nicht rechtsmissbräuchlich oder treuwidrig (vgl. <ref-law>) : Diese machte im Einspracheschreiben vom 13. Januar 2010 - d.h. nach Eintritt der Fälligkeit der umstrittenen Beitragsforderungen (E. 4.4.3) - hauptsächlich geltend, die Geschäftstätigkeit sei auf den 1. Januar 2008 verändert worden, weshalb aus der (jüngeren) Homepage nichts für die vorangegangene Zeit abzuleiten sei; damals habe die Firma "über kein entsprechendes Inventar und Maschinenpark" für Hoch- und Tiefbau verfügt. Lediglich aufgrund dieser Behauptungen, ohne sich auf entsprechende Unterlagen stützen zu können oder solche auch nur angefordert zu haben (vgl. E. 4.4.2), revidierte die Stiftung FAR ihre bisherige Auffassung insofern, als sie mit Schreiben vom 22. Januar 2010 eine Unterstellung erst ab 1. Januar 2008 annahm. Dies kann der Beschwerdegegnerin nicht als qualifizierte Meldepflichtverletzung angelastet werden. Ebenso kann von einer Arbeitgeberin nicht verlangt werden, ohne Anlass eine Einschätzung der Stiftung FAR, welche diese nachträglich als falsch ansieht, vorab zu "berichtigen", insbesondere wenn sie diese nachträgliche Auffassung nicht teilt. Damit steht der Berufung der Beschwerdegegnerin auf die Verjährung, wie sie im vorinstanzlichen Verfahren erfolgt ist, nichts entgegen.
4.6. Bei dieser Sach- und Rechtslage ist die Auslegung der kantonalen Zuständigkeitsvorschrift, insbesondere hinsichtlich der numerisch richtigen Besetzung des Verwaltungsgerichts (gemäss Rubrum: Zweierbesetzung; vgl. Art. 56 Abs. 3 des bernischen Gesetzes vom 11. Juni 2009 über die Organisation der Gerichtsbehörden und der Staatsanwaltschaft [GSOG; BSG 161.1]), nicht willkürlich (zur Auslegung und Anwendung kantonalen Gesetzesrechts vgl. Urteil 8C_267/2010 vom 24. August 2010 E. 2). Von einer Verletzung des Anspruchs auf den verfassungsmässigen Richter gemäss <ref-law> kann nicht die Rede sein (SVR 2013 BVG Nr. 15 S. 58, 9C_782/2011 E. 4, nicht publ. in <ref-ruling>). Die Beschwerde ist unbegründet.
5.
Dem Ausgang des Verfahrens entsprechend werden die Gerichtskosten der Beschwerdeführerin auferlegt (<ref-law>). Die Beschwerdegegnerin hat Anspruch auf eine Parteientschädigung (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'400.- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 17. Oktober 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Dormann