Guidをランダムに生成してアプリ内で重複しなければそのまま返す
重複してるならリトライを繰り返して重複しなくなったらそれを返す
最大試行回数を超えたら例外を投げる

この例外の名前はなにがいいと思いますか？
ちなみに.NETで開発しているので標準にドンピシャな例外があればそれがベストなのですが…