This is already done.  The removal of the entries from the datatree is 
done in IMP_Message::delete().  This gets called when deleting 
messages manually from the trash folder, and this is the function used 
to delete messages when the purge_trash maintenance task is run.

Would make sense, or is it possible at all, to also remove the entries 
when purging the Trash folder, either on demand or by a maintenance 
task?

IMP already deletes these entries when the message is permanently 
deleted.  The entires are not deleted if the message is sitting in 
your Trash mailbox (if used) so watch out for that.  Also, there was a 
bug in the framework DataTree code that was preventing the entires 
from being correctly deleted from the sql datatree backend - this has 
been fixed now.

When replying messages horde records some information to 
horde_datatree and horde_datatree_attributes tables like the date of 
reply. When these replied e-mails deleted these records stays still in 
the database. In time this makes these tables and DB become larger and 
larger. As a result when you want to read an e-mail some queries made 
to these tables and these queries runs slower because of the DB size.

When deleting e-mail these records must be deleted too or some 
maintaneince must be done periodically.