>Apesar de que cada GUID gerado não possui nenhuma garantia de ser único, o número total de chaves únicas (2<sup>128</sup> ou ~3.4×10<sup>38</sup>) é 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 5x10<sup>22</sup> estrelas, cada estrela poderia ter ~6.8×10<sup>15</sup> dos seus próprios GUIDs.

Fonte: [Wikipedia][1]

Segundo [essa resposta][2] no SO há 1% de chance de colisão se gerar 2.600.000.000.000.000.000 GUIDs.

E [nessa outra][3] parece mostrar como criar uma colisão. É bem difícil. Demora absurdamente.

[Artigos][4] [relevantes][5] do Raymond Chen. E lá tem links para mais uma das [excelentes séries do Eric Lippert][6].

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][7].

  [1]: http://pt.wikipedia.org/wiki/Identificador_%C3%9Anico_Global
  [2]: https://stackoverflow.com/a/184897/221800
  [3]: https://stackoverflow.com/q/1705008/221800
  [4]: http://blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx
  [5]: http://blogs.msdn.com/b/oldnewthing/archive/2012/05/23/10309199.aspx
  [6]: http://blogs.msdn.com/b/ericlippert/archive/2012/04/24/guid-guide-part-one.aspx
  [7]: https://pt.stackoverflow.com/a/21930/101