Have a report about the loss of your passport taken at a Malaysian Police Station.

Present this report, two passport photos and, if possible, an alternative proof of identity (e.g. ID card) when applying for a replacement travel document at the Embassy.

With the new travel document and police report record from the police, you must obtain an exit stamp from the Malaysian Immigration Department in Putrajaya before leaving the country. More information can be found here (in German).

Notice:

The Embassy will generally issue you with a “travel document as passport replacement” to return to Germany. If you need a temporary passport for travel to other countries, the Embassy needs authorization from the competent passport authority in Germany. The processing time can be between 1 to 2 days, but sometimes it takes longer.

Validity and Revalidation of Malaysian Visa

The Embassy points out that according to Malaysian law, a Malaysian visa automatically loses its validity if the passport containing the visa becomes invalid. This is the case, for example, when a new passport is issued and the previous passport is invalidated. You will then have to apply for the visa to be transferred into your new passport with the Malaysian Immigration Department.