運転免許証の住所変更に行こうとして、紛失(の可能性高い)に気付きました。と

運転免許証の住所変更に行こうとして、紛失(の可能性高い)に気付きました。
とりあえず手続きに行こうと思うのですが、この場合は新しい、
変更予定の住所の最寄りの警察署で良いんでしょうか？
紛失手続きは交番でも出来ますか？
落としてしまったみたいなんですが、全く心当たりがないんです・・・
落としものや忘れものを無くすコツってありますか？

紛失届けは交番でも大丈夫ですが、再交付手続きになると運転免許の手続きは都道府県によって違います。
新しい住所地で良いですが、例を挙げれば、東京都は試験場のみで、神奈川県や埼玉県も試験場のみですが、
千葉県は即日交付を希望しなければ県内全ての警察署でも再交付の手続きが可能です。
警察署で手続きが出来る所でも住所地を管轄する警察署のみになる所もあります。
警察署が置かれていない地域にある、幹部交番と呼ばれる大きな交番は再交付手続きなどの運転免許手続きが出来ると思います。
他都道府県からの転入（住所変更）を伴う再交付手続きになると、受付時間が違ったり後日交付になったりしますから、
紛失届けを出した時に再交付手続きの仕方（必要書類や場所や時間）も聞いて来ると良いと思います。

転居先の最寄の警察署で全部できます。
住民票(前住所と現住所の記載してあるもの)を持って再発行してもらうと
よいでしょう。(顔写真ももしかしたらいるかも)
もし昔の免許証がでてきたら古いほうの免許証を返納しましょう。
悪用するととんでもない状況になってしまいますから。

変更予定の所で良いと思います。
沖縄から北海道に引越しした人を、わざわざ沖縄まで行かせるような非道な法律はないと思います。
詳細は電話して聞いてみて下さい。