@WilDD: first and foremost, congratulations on, and thank you for a great product. One humble feature request: search. (My wife has 100s of DVDs, and scrolling v. searching becomes very laborious, very quickly.) If this feature already exists, and I'm just missing it, please let me know.
I will look into the search function, as this can be very useful.
I don't know how you have your videos categorized, but you can probably reduce a lot of navigation by categorizing or splitting up your videos. Whether you use directory structure, or an xml file, you can divide your videos into groups, or categories, which will allow you to quickly skip through videos and select a particular category which contains the video you want. You can also divide them up alphabetically, with each letter of the alphabet being a category. This way you can quickly skip through the alphabet to get to (say) the Ts to get to Titanic. You can categorize them to however suites you (and your wife) best.