The 2 messages implies you have a 'View' filter in place.
Add looks at the entire DB to generate the message. Search respects a Virtual Library.
Be sure All Books is where you are searching (Look at the Left side of the search bar. Click: It should say None next to the tick))
|