I noticed the sites I deleted where not back upped as expected. I took a look at the sources and found that at installation the following happens:
- The delete event receiver is attached to every existing site collection and site
- A feature which adds the event receiver to a site is stapled to every known site template.
The second part is the problem. Any new site collection or site based on a custom site template provisioned after the Recycle Bin feature is activated will not be back upped.