Faits : A. A.a. Entre 2001 et décembre 2006, B._ SA - dont l'administrateur unique est A._ - a été l'organe de révision de Y._ SA, société dont l'animateur est X._. Dans ce cadre, des factures d'honoraires trimestrielles de 2'259.60 fr. ont été adressées à Y._ SA entre novembre 2001 et mars 2004; celles-ci ont été régulièrement payées. En décembre 2006, le siège de B._ SA a été transféré à Zoug et sa raison sociale a été modifiée en C._ SA. Son administrateur unique - A._ - a été radié et remplacé par D._. C._ SA a réclamé, en avril 2009, à Y._ SA le paiement des factures d'honoraires des trois derniers trimestres 2004 et de l'année 2005. Une procédure judiciaire civile en a découlé (C_1). Au terme de celle-ci, la seconde société a été condamnée à payer à la première 15'817 fr. 20 avec intérêts à 5% dès le 6 août 2009 (cf. notamment l'arrêt 4D_91/2012 du 21 mars 2013); en particulier, il a été retenu que la preuve de l'existence d'une convention portant sur la gratuité des services de la première en faveur de la seconde n'avait pas été apportée. A.b. Le 31 mai 2012, C._ SA a assigné Y._ SA en paiement de 117'230 fr. 20, intérêts à 6 % dès le 30 octobre 2006. La première alléguait avoir développé, entre le 24 septembre 2002 et le 18 juillet 2006, une importante activité de conseils, notamment juridiques en lien avec des procédures civiles en France, en faveur de la seconde; cette procédure est actuellement pendante sous la référence C_2. A.c. X._, en sa qualité d'administrateur de Y._ SA, a déposé, le 11 novembre 2013, plainte pénale contre A._ et D._ pour faux dans les titres et escroquerie; il leur reprochait en substance d'avoir établi une série de factures, antidatées du 29 juin 2004 au 31 décembre 2005 pour des honoraires trimestriels. La partie plaignante soutenait qu'il avait pourtant été convenu que ladite activité ne serait pas facturée en raison des relations privilégiées existant entre son administrateur et A._. Tel serait également le cas de la facture de 117'230 fr. 20 prétendument émise le 30 septembre 2006. Le 21 novembre 2013, le Ministère public de la République et canton de Genève a ouvert une instruction pénale contre A._ pour escroquerie et faux dans les titres (cause P_1). Au cours de l'instruction, A._ a été entendu le 28 février 2014, les dossiers des deux causes civiles ont été versés au dossier pénal et un séquestre notamment des comptes pour les années 2004 à 2007 a été ordonné au siège zougois de C._ SA. L'enquête a permis d'établir que cette société n'avait qu'une boîte aux lettres à Zoug, que son adresse était à Genève, dans les locaux de E._ SA - dont A._ était l'administrateur - et que ce dernier était son ayant droit économique. A.d. Y._ SA et X._, par l'intermédiaire de leur avocat, a déposé une nouvelle plainte pénale le 24 juillet 2014 à l'encontre des administrateurs de C._ SA (procédure P_2); en particulier, il y était allégué qu'aucune activité n'avait été déployée par C._ SA pour Y._ SA durant les années 2002 à 2006. X._ et A._ ont été entendus le 22 août 2014, respectivement le 26 septembre suivant. A.e. Les causes P_1 et P_2 ont été jointes le 9 octobre 2014 et le Procureur a averti, ce même jour, X._ qu'il entendait classer les procédures, le litige paraissant avoir un caractère civil prépondérant. Par courrier du 10 novembre 2014, X._ a notamment soutenu que A._ lui devait plus de 3'000'000 fr. pour des opérations immobilières, rappelant également l'accord relatif à l'absence de facturation; il a de plus allégué que le second aurait menti à de multiples reprises devant les juges civils et pénaux, pouvant ainsi s'être rendu coupable de fausse déclaration d'une partie en justice et de faux témoignage. Par ordonnance du 17 novembre 2014, le Ministère public a classé la procédure; il a en particulier indiqué que le travail effectué jusqu'en 2006 n'était pas contesté et, ainsi, il n'y avait pas de dessein d'enrichissement illégitime, élément constitutif des infractions de faux dans les titres et de l'escroquerie. B. Le 17 juin 2015, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours intenté par X._ et Y._ SA. Elle a considéré que ceux-ci ne disposaient pas de la qualité pour recourir s'agissant des éventuelles infractions de faux témoignage ou de fausse déclaration en justice, eu égard à l'absence de conséquence dommageable. L'autorité cantonale a ensuite retenu que les factures contestées ne constituaient pas des titres permettant l'application, le cas échéant, de l'art. 251 CP. Elle a ensuite estimé que l'infraction d'escroquerie n'était pas réalisée par leur production, faute notamment d'astuce. C. Par acte du 19 août 2015, X._ et Y._ SA (ci-après : les recourants) forment un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant à son annulation et au renvoi de A._ devant le tribunal compétent. A titre subsidiaire, ils demandent le renvoi de la cause à l'autorité précédente afin qu'elle statue sur le fond des éléments qu'elle a déclaré irrecevables.