How is this "message" being displayed? As a modal dialog? If so, can the modal dialog be dismissed? Do you consistently see the "The data area passed to a system call is too small" error?
Please post the info from Help | About | Install Info (or email to
support@kinook.com). Just out of curiosity, is the IE 7 beta installed on this pc?
You said that that restarting Ultra Recall often isn't sufficient, persisting until rebooting. What if you restart Ultra Recall while holding the Shift key (to prevent a database from being opened)?
Another test once you have received this error would be to create a shortcut that opens a specific database at the root item item (select the root item and choose Item | Create Desktop Shortcut) and open it via the shortcut.