Apesar de que cada GUID gerado não possui nenhuma garantia de ser único, o número total de chaves únicas (2128 ou ~3.4×1038) é tão grande que a probabilidade do mesmo número ser gerado duas vezes é muito pequena. Por exemplo, considerando que o Universo Observável contém 5x1022 estrelas, cada estrela poderia ter ~6.8×1015 dos seus próprios GUIDs.
Fonte: Wikipedia
Segundo essa resposta no SO há 1% de chance de colisão se gerar 2,600,000,000,000,000,000 GUIDs.
E nessa outra parece mostrar como criar uma colisão. É bem difícil. Demora absurdamente.
Artigos relevantes do Raymond Chen. E lá tem links para mais uma das excelentes séries do Eric Lippert.
Algumas pessoas talvez não entendam que GUID é composto por tantas informações distintas que faz um esforço tão grande para ser único que a maioria das outras tentativas que alguém pensar serão piores, inclusive as citadas nesta página. Não estou dizendo que GUID é a melhor solução para o problema real do AP, apenas reforçando a ideia que ele é mais único do que o número frio indica.
Se a Microsoft acha que está bom para ele usar o GUID em muitas aplicações suas para garantir a unicidade, quem sou eu para dizer que não serve?
Falo mais disto nessa resposta.