After a couple of days of analysis I found the problem and the solution.
The problem was occurring only at the time of uploading the package, where the anonymous authentication kicks in (in IIS) and it delegates the authentication process to WCF. In theory only NTFS will interfere with the WCF authentication if a user doesn't have the right access level to a folder, for example, the service might be trying to access (Temp, Packages, etc...).
So I confirmed that the folder permissions were right. Then I tried fiddler and the only think I could confirm was that the error was happening when hitting the stream upload binding in the ImportExport service.
What I did to resolve the issue is to use procmon.exe in windows and filter the results to only see the operations done by the w3p service, which turned out to be very helpful, since I started to see "Paths" with the text Rejected-By-UrlSca it, and a bunch of 404 errors on fiddler again.
After some research I came accross this post regarding the URL scan ISAPI filter, which indeed was the cause of the error:
Rejected by URL Scan 404 Errors
After following the steps in such post, I removed the ISAPI filter with URLScan in IIS for the SDL Tridion web application.