That swapping around the dependencies you suggested is actually the first thing I thought of and the first thing I tried when I was debugging this yesterday. It didn't make any difference and the same problem occurred.
However just now after seeing your response, I created a new docker-compose file with the dependencies swapped around, now it does work as expected. So that was the problem.
In regard to how to implement a feature to fix this, I think the only way to do it would be to somehow have a notification from the docker daemon to alert ofelia when a new container has started on the host, then ofelia can check if it has the right labels, and can register a new scheduled task.
That sounds like its easy on the surface, but likely hard to properly implement.