Set up IMAP, migrate all your folders and old messages over, then set Eudora and the iPhone to IMAP.

The phone defaults to only downloading the newest 200 messages in a folder, and will only grab more if you manually scroll to the bottom of the mailbox. It also only automatically checks the inbox. With IMAP, if you nuke a message it will move to the Trash folder on both the phone and Eudora. IMAP gives you the same state in all places.

Eudora, like pretty much any IMAP desktop client, will download all your mail and cache it locally to make searches pretty quick.

If you are setting up your own mail server, I'd highly recommend an IMAP server that uses maildir formatted mailbox, and not mbox, especially with how much mail you have. The difference is that maildir creates a folder then makes a file for every message. Moving, deleting, and other common operations are much less IO intensive on the server since it doesn't have to pull a message out of the middle of a solid mbox archive. I've run Courier IMAP with MurderFS, err, Riser for quire a few years with no issues. Even migrated the 10 or so users between 4 servers now.