OK, I think I figured it out.

Strange as it may seem, it looks like the Handler from the first Service instance wasn't destroyed, somehow it persisted in memory with some data from the first instance, including said string. When the Service was created the second time, it probably got the Handler from the first time, with its data.

Sounds like a phantasmagoric explanation. In any case, I can say for sure that I called killProcess at the end of Service.onDestroy, and it solved the problem. Now it works as intended the second and third time and so on.
So this is the best explanation I have. If somebody can figure out a better one, please tell me about it.

Also, is there a better way to destroy a Handler explicitly, other than killing the whole process ? Sounds like a nuclear solution to me, I wouldn't like to use it unless I have to. But I searched and it seems I can't get rid of the Handler otherwise.