I just read these two posts:
http://blogs.msdn.com/simonince/archive/2008/08/15/strongly-typed-primitives.aspx
http://www.thejoyofcode.com/Avoiding_Primitive_Obsession_to_tip_developers_into_the_pit_of_success.aspx

And that reminded me about something we recently did. One system we're working on uses a lot of string identifiers for many different types of objects. There are many, many of these stored and passed around, so keeping things efficient was of high concern. 

The downside of string IDs (really, using any common type as an ID) is that it's legal to pass any primitive of the same type. Strings and integers abound, both as IDs of other classes, as well as general use. So it's not unimaginable that someone could pass the wrong parameter some where. This could lead to runtime crashes or unexpected results (if the ID is actually a real record of another class of object). Finally, using common types for IDs reduces usability. The signature "public void Delete(int id)" leaves a lot to be desired.

We wanted to hit all these issues, in addition to keeping things simple. There are times when untyped data needs to be converted, and this should be easy and clear. We wanted to avoid having to define new types when we had new classes of objects to identify It is also customer-visible code, so C# is used.

Using a reference type was unacceptable, because it'd add at least 12 bytes overhead (I think more on x64). Using a struct fixes this, in addition to dealing with silly nullability issues. [If a type can be null, it should always be explicit. C#'s "references types can be null" makes this hard.]

The end result was quite simple. Wrap a string in a structure so equality and hashing pass through. But, take advantage and remove case/cultural sensitivity (since in many systems, data IDs are not case sensitive). Provide explicit conversions so you can easily convert to and from strings, but never by accident. (If the conversions were implicit, you're back in the starting point.) Finally, add a generic parameter that is never used. The generic parameter gives you distinct types without having to define them. Now the APIs can look like:

    public void Delete(Id<Product> id)...

    Dictionary<Id<Group>, List<Id<User>>> members...

When you do have hardcoded IDs, as the blog entries I mentioned do, you can convert easily: (Id<User>)"Admin". Nulls are treated as empty, all the time (empty may be a valid value anyways).

When a truly optional ID is needed, use nullable types: "Id<Whatever>?". This fully captures how values are handled. This is vastly better than "It's a reference type, so maybe null is allowed. Or maybe null will crash. Empty string might be considered null, or maybe empty string means optional." With explicit nullability, the type system says it all.

The best part is that there should be pretty much no overhead. I'd expect the equality functions to be inlined, and there's no memory overhead, since the struct is simply a string reference.

public struct Id<T> : IEquatable<Id<T>>
{
    public Id(string name) {
        this.name = name ?? "";
    }
    readonly string name;
    
    public static explicit operator string(Id<T> x) { return x.name ?? ""; }
    public static explicit operator Id<T>(string s) { return new Id<T>(s); }

    public override bool Equals(object obj) {
        return
            !(obj is Id<T>) ? false :
            ((Id<T>)obj) == this;
    }

    public bool Equals(Id<T> other) {
        return other == this;
    }

    public override int GetHashCode() {
        return (name ?? "").GetHashCode();
    }
    public override string ToString() {
        return name ?? "";
    }
    public static bool operator ==(Id<T> a, Id<T> b) {
        return StringComparer.InvariantCultureIgnoreCase.Compare(a.name, b.name) == 0;
    }
    public static bool operator !=(Id<T> a, Id<T> b) {
        return !(a == b);
    }
}