In Germany, records on birth, marriage and death are kept by the ''Standesamt'' (registrar’s office).
Depending on the kind of record, they are kept at least for:
- 110 years (birth records)
- 80 years (marriage records)
- 30 years (death records)
at the Standesamt which has the duty to make corrections and additions to them during this time (e.g. adding a hint on someone’s death in his birth record). See Personenstandsgesetz: § 5 Fortführung der Personenstandsregister. Afterwards, they are handed over to the local archive, in this case Stadtarchiv Stuttgart.
So if the man’s birth date is known, you theoretically can request the birth record from the Standesamt in Stuttgart. It will provide you with a hint on place and time of death as well. Why theoretically? Before the records are handed over to the archive (see time periods above), rigorous access restrictions apply. Information is only provided to the person of the record himself/herself, spouses, life-partners, ancestors and descendants (§ 62 (1) Personenstandsgesetz: Urkundenerteilung, Auskunft, Einsicht).
Otherwise can only access a record, if everybody who is mentioned there (this includes e.g. both partners in a marriage record) is dead for at least 30 years and you can prove legitimate interest (“berechtigtes Interesse”), as detailed in (§ 62 (3) Personenstandsgesetz: Urkundenerteilung, Auskunft, Einsicht).
How to proceed depends if you are entitled for access, e.g. by being an descendant. I outline a conservative research strategy, without such a connection.
You know the man’s name and his day and date of birth → most likely not helpful due to legal restrictions right now. You might search in death records at the archive older >30 years for now. Every year, another yearly issue is added
You know the woman’s name, and her date of death. I assume she died in Stuttgart as well. Contact the local archive and get the death record. The death record indicates the birth date and place. Get the birth record from the Standesamt of the place where the woman was born (as you can prove now that she is dead for >30 years). This record should give hints on the marriage and maybe on children.
Always request a full copy of the original entry („vollständige Kopie des Registereintrages samt Anmerkungen")! (This is vital, as they sometimes only fill a modern form with the historic data)