I have followed the Manual on Short URLs and it works perfectly except for yet-to-be-created pages.
For example, on Main_Page there is a link to the uncreated page Sub_Page, this URL points to my 'ugly' MediaWiki installation folder and uses an ugly url:
mysite.com/mediawiki/index.php?title=Sub_Page&action=edit&redlink=1
It should look like this:
mysite.com/wiki/Sub_Page&action=edit&redlink=1
The rest of my website uses the prety URLs, so I have no idea why this is happening.
How do I fix this?