Alright, here's what I have to ask.
1. How much did you pay them exactly?
2. How many cameras were there?
3. Does it really look bad, or just a lil' grainy?
If it does in fact shoot interlaced and it was de-interlaced properly you shouldn't be able to tell. My company shoots 1080i and de-interlaces all the time. It looks flawless in 1080p
4. If it does look grainy, was it dark during the grainy parts?
Sometimes if it is really dark and gain on the camera isn't set right or the camera doesn't have good gain settings that can effect it (with little the camera man nor the company can do aside from warn you to get a pro lighting package).
5. Did they charge for "HD" or "1080p HD"?
Technically HD resolutions are 480P, 720i, 720p, 1080i, and 1080p. Normally 480p and 720i aren't used because they are a (sort of) "Grey Area" and don't look all that much improved from the average Tube TV/ Monitor resolutions.
6. Can you get us a few stills?
This is not going to achieve much, but it may give us some indication. If the lighting is dark enough, or it's kinda pixelated or something we'll be able to see indications of what (if anything) went wrong. I know I can normally spot differences in mistakes made in filming, post, or authoring.
My company notifies our clients of the exactly the type of equipment we use from camera to authoring software in our contracts. I'm not very familiar with how other companies contract their work, but it would seem like we were cheating the client if information was not given to them. Hell, then for all you know they could show up with cheap 720p home video cameras. If they were not completely upfront with you, shame on them.