The following refers to 1.6.1 stable.

When deleting a template (haven't tested for hosts), the tables applications gets not cleaned up.
That is one source of the issue when linking more than one template to a host.
To get only the correct records i used:
a.applicationid, a.name, a.templateid from applications a, hosts h where h.hostid = a.hostid
And veryify against the the table table applications. The difference is imho garbage.

It seems that items_applications gets also not cleaned up. Given that it uses applicationid i assume i must not have more entries that applications. However i still do not know, yet
In my case applications had ~ 300 records where item_applications had ~3400.

To get only the correct records i used:
select i.itemappid, i.applicationid, i.itemid from items_applications i, applications a where a.applicationid = i.applicationid

//EDIT
I just removed hosts with items that have an application and can see that items_applications gets cleaned up.
However: - When adding an application (other than other) to an item i get proper records but if there is no application and it defaults to other i see strange increase.

It seems this might be related to the template linking issue with more than one template.
ERROR: Conflict between selected templates