Did you check if it is indeed pie.htc which doesn't load or maybe the CSS file referencing it?
I've been using CSSPIE for years with SharePoint 2007/2010/2013 even on sites with anonymous access enabled without issues.
The first thing I would check is the HTTP request pipeline using a tool like Fiddler or the IE F12 developer tools.
Since you didn't mention the SharePoint version, if SP 2013 make sure it's at the right place in /_layouts/15/
...
I usually put pie.htc inside the /_layouts/15/styles
folder on SP 2013 and /_layouts/styles
on SP 2010.
UPDATE
Based on your comment it sounds like the CSS is loading fine, but pie.htc just doesn't take.
Using Fiddler should tell you what kind of access error on pie.htc occurs. Is it a 404 (not found) or a 401 (access denied).
If a 401, how did you deployed pie.htc? If you copied it manually check if the SharePoint Web Application Pool account does have proper permissions to read the file. I've seen it happen occasionally that the file permissions didn't match.
If a 404, how does your line in the CSS file look like? Something like behavior: url("/_layouts/styles/pie.htc")
should work. Using an absolute path like behavior: url("http://server/site/_layouts/styles/pie.htc")
can get you in trouble depending on the IE security zone settings.
Also, try to avoid using a relative path like behavior: url("../_layouts/styles/pie.htc")
as it might fail on list view and form pages because they are a level deeper.
Last but not least, since you mention it fails on some users, make sure to test on a single machine with the same IE using two different users, by logging out/in using the SharePoint Welcome dropdown menu (the one showing the user name on the top right).
Also, make sure the users where it fails are running IE in the "IE 8 compatibility" mode. This should be the default for SP 2010 except you modified the masterpage.
I know, lots of things to check but it could be several things ;-)