UR should continue to provide excellent performance with that many nodes. See the following for more details:
http://www.kinook.com/Forum/showthread.php?threadid=731
http://www.kinook.com/blog/?p=18
http://www.kinook.com/Forum/showthread.php?threadid=709
The two UR databases I use on a regular basis currently have ~ 4,500 and 11,000 items/links, respectively, and startup and quick searches are still nearly instantaneous (and one is even located on a network share).