I don't think you are ever required to have third-party 'information' reports other than those used as evidence of withholding, as long as the information you put on your forms and schedules is correct -- although in some cases this is difficult or impractical without the third-party info. Your fiance (and you) need to be certain that the contributions were made in or promptly after (and designating) the relevant years (account statements can mostly cover that, but also see below) and were in fact NOT deducted (that's the hard part).
Returns/transcripts: You say you ordered (and got) a 'tax transcript' for 2013. I'll guess that means your fiance didn't keep copies of their returns (even for the 3-year standard 'audit' period!), and now understands why that would have been a good idea. (In fact keeping a copy of anything you file with any government agency is a good idea, but that is out of scope for money.SX.) To be specific I hope you mean a 'tax return transcript' not a 'tax account transcript' because the latter wouldn't help here. I don't know if even the former shows 8606 since it isn't strictly part of your return, but it definitely should show if an IRA deduction was taken since that's a line item.
Form 4506T allows you to request return transcripts and says they are available "for the current year and ... prior 3 processing years." This may be out of date; I believe this limit was due to their old 'master file' system which they finally last year (after IIRC more than 20 years of trying!) got replaced with an actual database system. You could try requesting further back and see if it works; at worst it costs you a few stamps. If not you can presumably get TY2012 (from PY2013) which may help a little. Did he do these returns himself, or use a preparer or online tax software e.g. TurboTax? Either of the latter might have some records that might be helpful. If nothing else, you can request of copy of the actual return from storage (not just a transcript) on Form 4506 (note no T), but that's $50 per return and takes 'up to 75 days'.
1099R/5498: For the rollover year, yes he should have gotten 1099R's from the closed accounts, as well as 5498 showing transfers-in and balance on the new account. Even if he didn't get or didn't keep these, they (both 1099R and 5498) definitely should have been filed with the IRS, as should 5498's for all previous years. Form 4506T also allows you to request separately a transcript of these forms (actually covering W-2 1099* 1098* 5498) in item 8, and it says (emphasis added) these 'may be [available] up to 10 years [back but not] the current year' (which last is fine for your case). If they have 10 years for your case that's presumably back to 2006, nearly the whole period you need. But the third-party reports can't tell you if a deduction was taken, because the custodian doesn't know. (Except for a Roth account, which of course they know is never deductible.)
Filing etc.: It's also not clear to me if you can file 8606 separately now, or only with an amended return (1040X) that doesn't actually amend anything in the return. The instructions are all written for the on-time filer, and say you must enclose 8606 if it is required for a year with the 1040-series return for that year if you file one, or if you aren't required to file a return you file 8606 by itself with its own signature 'under penalties of perjury' to the same location. Thus if you had a filing requirement which you did meet, it's unclear if you can late-file 8606 alone, or you need to file 1040X to 'carry' the 8606, in which case you need at least basic figures from those back-year returns which you are missing and may not be able to get.
The thing that worries me is that if the contribution was actually deducted, even though he doesn't remember it, if he now swears to a statement that it wasn't deducted that moves him from 'not smarter than the average bear' to apparently intentional (and hard to rebut) perjurer. If he (and you once you're married, because married means joint and several liability for Federal tax) gets audited, this will be a difficult position to defend.
And finally, publication 590 (now split into parts A and B) states
Penalty for failure to file Form 8606. You will have to
pay a $50 penalty if you do not file a required Form 8606,
unless you can prove that the failure was due to reasonable
cause.
Since IRS computer matching could detect this -- they had 5498 showing contribution to a traditional account and a return with no deduction taken --
I would expect them to send a notice. OTOH I would not expect
them to try to actually collect, since that involves humans who are
much more expensive than computer notices.
Would, and does, he remember a 'soft' notice with no collection action?
In short (too late): What the two of you do is your (joint) call, but in your place I would either:
consult (for pay) a CPA specializing in tax or an Enrolled Agent, that is someone whose actual paying job is to know about tax law and regulations and IRS processes, not strangers on the Internet of unknown competence or caninity; or
file for as many years as I can document, using return transcripts or other sources if possible and paid return copies if necessary, which probably means back to 2009, and write the rest off as a painful learning experience.
Good luck.
