>現在3000アカウント位あるんですが、relay_recipient_mapsを書いた場合
>検索速度的には大したことないのでしょうか?

relay_recipient_maps の参照方法にもよるけど、たいてい気にする必要はない。
ただし、3000アカウントだとまさか /etc/passwd じゃなくて LDAP か何かで
ユーザ管理してると思うけど、LDAP サーバの設計/設定がマズいのに
relay_recipient_maps で LDAP を参照させるとひどく遅くなるかもしれない。
この場合、postfix 以外のところでも遅いはずなので、まずそっちを直す必要あり。