There are multiple discussions online regarding this problem, mostly regarding redirecting the 404 error page. However the solution is SUPER simple - RTFM (the following answer appears in the WordPress permalink setting page): add a file "web.config" containing the following lines
<?xml version="1.0"?>
<configuration>
<system.webServer>
<rewrite>
<rules>
<rule name="Main Rule" stopProcessing="true">
<match url=".*" />
<conditions logicalGrouping="MatchAll">
<add input="{REQUEST_FILENAME}" matchType="IsFile" negate="true" />
<add input="{REQUEST_FILENAME}" matchType="IsDirectory" negate="true" />
</conditions>
<action type="Rewrite" url="index.php" />
</rule>
</rules>
</rewrite>
</system.webServer>
</configuration>