It looks like 12% of the time is being spent figuring out what rows to insert, and 88% actually doing the insertions.
So I think that index maintenance is killing you. You could try adding a sort to your select so that rows are inserted in index order, or inserting in batches in which the batches are partitioned by service_id (which is almost the same thing as sorting, since service_id is the lead column)
In that case, partitioning the original table by service_id % N would help, since the index would be much smaller, right?
N would have to be reasonable - 10, 100, 256, or something similar.
