I have had this exact experience with Expedia Special Rates(which is why I have previously posted on Expedia Special Rates). Note not all Expedia bookings are this type so double check yours.
My expense reports when booking these cheaper rates were at first an issue with my accounting team. Then I explained (and the Expedia printout shows) that this is a PREPAID rate. Meaning that this is a valid reciept. And that I saved the company money (always gets their attention)---now it is golden. Remember not all Expedia rates are prepaid but when you run into this issue that is why. (Which is why you Hilton issue might have been different).
I have also called Expedia (1-800-expedia) to get this verified.
Now the customer service at this hotel might (and likely is) still an issue.
So if you do the print out and have even half rational people in your accounting dept you will be OK.
[This message has been edited by 200 ngts/ 200 legs/year (edited 02-01-2002).]