It turns out that the problem wasn’t WP per say but that mod_rewrite was being forbidden because of some server settings. I didn’t realize it until the server guy sent over an error log that was filled with messages containing:
Options FollowSymLinks or SymLinksIfOwnerMatch is off which implies that RewriteRule directive is forbidden
To make it work, he had to activate FollowSymLinks and SymLinksIfOwnerMatch in one of the server config files (I’m not sure which):
<Directory [REMOVED]>
Options +ExecCGI +FollowSymLinks +SymLinksIfOwnerMatch
AllowOverride None
#Options None
Order allow,deny
Allow from all
</Directory>