The next version of ASP.Net will make it easier to specify an exact clientID for the control. At the moment, you have several options to work around this issue:
Inline Styles
<asp:Label runat="server" ID="MyLabel" style="..." />
CssClass
Just use a css class, as you mentioned in your quesiton. Nothing stops you from making those unique if you have to.
Write a handler to serve your style sheet
When you write your style sheet, leave placeholder in the file for client IDs. Then use an http handler to substitute in the actual rendered IDs on each request. This isn't exactly simple because the style sheet request is separate from the html page request, but it is certainly possible and so worth mentioning.
Use a container
Since a label renders as a span tag, if that span is unique within a specific naming container you can select it that way:
<div id="MyContainer"><asp:Label ID="MyLable" runat="server" /></div>
And in your style sheet:
#MyContainer span { /*...*/ }
Use a container + a class
If the container is not specific enough, you can use the class just to narrow it down within that container:
<div id="MyContainer"><asp:Label ID="MyLable" runat="server" CssClass="MyClass"/></div>
and in your style sheet:
#MyContainer span.MyClass { /*...*/ }