about 5 seconds on my test installation (3000hosts)
about 40-60 seconds on production (15000hosts)

explain from mytop on test install:
EXPLAIN SELECT max(ht.hostid) as hostid, ht.templateid FROM( SELECT count(htt.templateid) as ccc, htt.hostid FROM hosts_templates htt WHERE htt.hostid NOT IN ( SELECT httt.templateid FROM hosts_templates httt ) GROUP BY htt.hostid ) ggg, hosts_templates ht WHERE ggg.ccc>1 AND ht.hostid=ggg.hostid GROUP BY ht.templateid:

• • • row 1 ***
      table: <derived2>
      type: ALL
      possible_keys: NULL
      key: NULL
      key_len: NULL
      ref: NULL
      rows: 3329
      Extra: Using where; Using temporary; Using filesort
    • row 2 ***
      table: ht
      type: ref
      possible_keys: hosts_templates_1
      key: hosts_templates_1
      key_len: 8
      ref: ggg.hostid
      rows: 1
      Extra: Using index
    • row 3 ***
      table: htt
      type: index
      possible_keys: NULL
      key: hosts_templates_1
      key_len: 16
      ref: NULL
      rows: 2904
      Extra: Using where; Using index
    • row 4 ***
      table: httt
      type: index
      possible_keys: NULL
      key: hosts_templates_1
      key_len: 16
      ref: NULL
      rows: 2904
      Extra: Using where; Using index