Can I be deported despite having a "Duldung"?

A "Duldung" is not a residence permit but rather the suspension of your deportation obligation. Having a "Duldung" does not eliminate your obligation to leave Germany, but only postpones it for a specific period. If your tolerated stay ("Duldung") expires or is revoked, you may be deported. A tolerated stay can be revoked when the reasons for its issuance are not valid anymore. If you, e.g. have been issued a "Duldung" because you did not have a passport and now can obtain one from your country, your "Duldung" may be revoked.

After the expiration or revocation of your "Duldung", in principle, you may be deported. Your deportation then may be carried out immediately and without any notice. Only if you have lived with a "Duldung" for more than a year, the authorities are obliged to notify you of your imminent deportation at least one month in advance. In this case, you will be sent a deportation notice.