Sigh… The problem with those AsyncTasks was caused by a bug elsewhere™. I had added a lock mechanism for the database access (multithreading, yay!) and the lock was not released in one crucial network call that updates the data oftentimes. Now it is fixed and all those AsyncTasks work just fine.
But, as I was debugging this I decided I should refactor a couple of the bigger tasks to be based on IntentService instead. That then prompted me to refactor one continuously running service to be based on the plain Service instead. There can be only one IntentService running at any given time. Once the previous one completes, the next one will be started. And if that continuously run service would be based on IntentService, that would effectively block all other IntentService work, making all that other work pointless.