The following is the conclusion of this issue. I'm not sure if it should be made into a JIRA or not for anyone else, but we have been able to resolve the problem.
For some unknown reason, wiki pages with spaces in the filenames stopped linking to their pages. The content of the pages was still accessible using the node browser, but they wouldn't link properly.
The alf_child_assoc table (cols child_node_name and child_node_name_crc) are the two columns that need to be corrected
child_node_name is the wiki page name which has been converted to lower case and has had spaces converted to _.
Our problem was that these spaces where converted to %20, which it didn't like.
It doesn't mind strange characters in the name, but %20 ultimately gets escaped itself, so the % becomes %25 and the 20 remains, so Alfresco actually tries to access %2520.
Also, this column has a maximum of 50 characters. Anything longer is cut at position 47 and ~~~ are appended.
child_node_name_crc seems to be a CRC32 of what alf_child_assoc would be, before it's truncated to 50 characters.