Airlines use Timatic to display information about visas necessary for particular travelers going (or transiting in) a specific place. Putting your information into the Timatic web interface yields this:
26FEB19 / 1441 UTC
National Zimbabwe (ZW)
Transit Saudi Arabia (SA)
Destination Zimbabwe (ZW)
ALSO CHECK DESTINATION INFORMATION ...
You should submit your application, with as many details of the denial as you remember.
You are not the first person who has mislaid, never got or plainly thrown away the denial letter. It is quite a normal thing even.
As long as you are open about the fact you got a denial, and tell when (as good as you can) so they can check back if they feel the need.
Not all Schengen countries stamp passports of residence permit holders; this depends on national practice. Germany (along with, for example, Switzerland and Slovenia) doesn't stamp passports of residence permit holders.
And being that you have a valid residence permit, that is what dictates how long you can stay, so you will have no problems exiting or re-...
Instead of sending the visa refusal with your application, write a note saying:
you're perfectly aware it should've been included
you don't have it
you asked for a copy
they claim not to have it either
They won't expect you to work miracles, they expect you to be honest. So be honest. Provide them with the details you have (like you have posted ...