I have a large (~1900 pages) website (Steamships.org) that has been
built up over time.  Begun in January 2000, it is showing its age.

After studying the traffic patterns, my research indicated that people
search for steamship information based on the steamship line such as
Cunard Line or White Star Line.  The current structure, is undergooing
changes as I have begun moving pages to a steamship line based
structure vs. a function based structure.  For example, Yesterday, I
redid the Allan Line section
(http://www.steamships.org/ships/allanline/index.htm) drawing from the
old Allan Line section
(http://www.steamships.org/maritime/steamships/allan_line/index.html)
plus postcards (http://www.steamships.org/lib/postcards/allan_line/index.html)
and books (http://www.steamships.org/lib/book/maritime/0771007205.html)
from the library section, etc.

Once I complete the reorganization of this website, it will far exceed
the capacity to use .htaccess redirects.  This leaves me with meta tag
refresh to the new page (with the content removed and a link to the
new page url) or removing the page from the server and allow my custom
error page to redirect them to the general area.

What is the best approch to use to keep not only the visitors from
getting confused, but also keeping search engines happy.