When visiting the link the pattern is, that for each page creation the block log is missing.

The "related" on that special page is using the pageid, but when the user block is done before the page is created the log entry gets a related page id of 0.

The special page must look also with the namespace/title to find the logs

The users were blocked before the user pages were created, so the block log entry that would appear on Special:RecentChangesLinked actually does not appear because its rc_cur_id is zero. Special:RecentChangesLinked checks for recent changes where the rc_cur_id matches the page ID of one of the pages in a category.

Is this something that used to work correctly or something that never worked? (Sounds like it's the latter?)
Can you explain what the impact is on editor workflows?