検索エンジンとかソーシャルブックマークとかについては考えてませんが、通常のサイトでは、
- リダイレクトさせたいのはユーザーじゃなくてサイト
- サイト側でユーザーの動向を把握したい URL は、自分のサイトと直接的に何らかの関係のあるサイトのはず
- したがって任意の URL へジャンプできるリダイレクタではなく、サイト内で確認済みの URL へのリダイレクトだけを許可
するようにしたらダメなんでしょうか？ つまり、リダイレクタに URL が与えられたら、それが内部に登録済みのものかどうかを検証してからリダイレクトする。（つかそうなってないと集計とかしにくいでしょ？）
もちろんユーザーが自分で URL を登録できる場合は危険な URL を登録されるかもしれないのでこれだけではダメなんですが、ちょっとそれを考え始めるとややこしいんで今回は除外します。
個人的にはリダイレクタは脆弱性だ！なんてことを言う気はないけど、問答無用で任意の URL にリダイレクトできるということであれば、それはちょっとアレだと思うなぁ。
[2007-01-30 追記]自サイト内で生成したリダイレクト用の URL かどうかは HMAC を利用して検証するのが性能面ではよさげ。DB にアクセスしなくても妥当かどうか判定できる。もちろん内部でのカウントなどの処理のためには、実際にリダイレクトする際には DB アクセスは必要（あるいはログを吐くだけという手もあるか？）なんだけど、パラメータの妥当性はその前段階で検証できるので、DB の負荷が減るということですな。しかしそうなるとリンクの際の URL はどんどんかっこ悪くなっちゃうんだな。そこはアプリというかサイト側の工夫の見せどころか。