Daily scheduled task randomly stopped working

are other jobs in the same queue processing ok?
can you move the task to a different queue and see if that changes anything?
perhaps create a completely new task doing the same function

Is it IAL replication? If not,

1. Temporarily change the schedule (e.g., run the task every hour instead of daily) to see if it consistently fails or if the issue is intermittent.
2. Change the queue or create new schedule task with deleting the previous one.

Thanks for your answers! We did a bit more research on the problem and we got a broader picture of what's going on:

1. None of the scheduled database tasks work even if their next execution time is updated correctly. This is not related to the queues, as there are scheduled database tasks in multiple different queues. And because jobs are run in different queues in particular order, we assume that creating a new queue for only scheduled database tasks is not possible.
2. Creating new tasks for the same function probably would be possible, but a bit hard as all the database tasks would need to be re-created and re-inserted to queue

I’m sorry, but now I am confused.

From your first post, I thought that you had one scheduled task which was failing to run correctly.
Now it sounds as though NONE of the scheduled tasks are running, and that there are many tasks which are not working.

Where you have added new processed to the queue, I presume this is in the batch queue configuration screen - have you  tried re-initialising the queue?

It is definitely possible to possible to move methods from one queue to another - but if you can run the job manually, that would suggest the queue is not the issue - as you say.

Have you checked permissions? Is either a user or a permission set granted to the database task? If a user is granted, is the user the same as the one used to create the task? Is the security cache up to date?

some screen shots of the current setup should help the community to help more if this is still a problem for you.

This was my mistake. At first we understood that only one scheduled background job did not work, but later we found out that none of the scheduled background jobs worked.

Yes, we have tried re-initializing the batch queues, but it did not fix the problem. 

The scheduled database tasks are run as IFSAPP, so I assume there should be no problem with permissions.

Check in Database Processes page that the database processes are activated and Last Date/Next Date are updating as they should.