Air Carrier departure from LAS described confusion regarding the Shead 7 SID; the crossing altitudes ATC vs. conventional; the NOTAM instructions and ATC's phraseology.

Narrative

We were assigned Shead 7 departure SID out of LAS. My First Officer and I reviewed and noted the NOTAMs for the Shead 7 departure. NOTAM No 1/242: Shead 7 departure; cross MDDOG at 9000'; ATC/at or above 9000';. Cross TARRK at 11000'; ATC/at or above 11000';. Our PDC cleared us to FL190 with SID restrictions. When I checked in with LAS departure; I heard the controller assigning unrestricted climb to previous traffic. Climbing through 5000';; I asked the Departure Controller about the NOTAM altitudes and which set applied to us regarding ATC vs. at or above altitudes. He replied with yes; comply with the NOTAM at or above altitudes and then stated climb unrestricted through 11000';. I read that back and understood that we were to climb unrestricted to 11000'; and then continue to climb to FL190 while complying with the rest of the restrictions. My First Officer had the same understanding and he was the pilot flying. Controller never said 'climb and maintain 11000''. ATC gave us a traffic alert at 12000' and instructed us to maintain 12000'. ATC notified us of a B737. We had said traffic in sight. There was not any TCAS conflict. We were given a phone number and advised by the controller to call it upon landing; for a possible deviation. I contacted the TRACON supervisor upon arrival. After hearing my explanation; he agreed to investigate further as well as listen to the tapes. He called me back to inform me that he concurred with our explanation. He acknowledged that the controller did not use standard phraseology. He also said that altitude busts unfortunately happen quite often in Las Vegas due to the complex altitude restrictions. I agree with that assessment. I think the communication issues coupled with multiple complex crossing restrictions are causing deviations and confusion. Standard; clear; and timely communication between the controller and pilot is crucial.In this case; my question about the NOTAM to the controller aggravated the problem. Next time; I will try to clarify the questionable NOTAMs on the ground to avoid confusion. I will also query the controllers about incomplete and suspect clearances.