I actually enrolled myself as a student in few courses, accessed them and still have empty Recently Accessed Courses block. Is that because I'm also the site admin? It would be nice to have documented all the prerequisites and rules that have to be satisfied for the course to be displayed in Recently Accessed Courses block. I use Moodle 3.6.3+ (Build: 20190315).
My problem was with Cron. When I set Cron properly, recently visited courses started to show up in Recently Accessed Courses block.