If I evaluate the same setq and define the same tasks, my result withe org-agenda tasks list are:

Global list of TODO items of type: ALL
Press ‘N r’ (e.g. ‘0 r’) to search again: (0)[A$
(1)TODO (2)DONE
test: TODO test1
test: TODO test2
test: TODO test3
test: TODO test4

I tested at this moment with Org version 9.5.2 on Emacs version 27.2

Le 5 avril 2022 07:44:25 GMT+02:00, Ihor Radchenko <yantar92@gmail.com> a écrit :
Sébastien Gendre <seb@k-7.ch> writes:

I've tested it, but the tasks with no deadlines are still on top of the list.

I am unable to reproduce on my side using latest stable Org.
I used the following example org file:
* TODO test1
* TODO test2
* TODO test3
DEADLINE: <2022-04-04 Mon>
* TODO test4
DEADLINE: <2022-04-06 Wed>
(setq org-agenda-sorting-strategy '((agenda deadline-down time-up habit-up priority-down timestamp-down category-keep)
				    (todo deadline-up priority-down category-keep)
				    (tags priority-down category-keep)
				    (search category-keep)))

The todo agenda buffer looks like:

Global list of TODO items of type: ALL
Press ‘N r’ (e.g. ‘0 r’) to search again: (0)[ALL] (1)TODO (2)DONE
  bug:        TODO test3
  bug:        TODO test4
  bug:        TODO test1
  bug:        TODO test2


Best,
Ihor