It's a common misconception that "Verify is visible" is testing whether or not the target UI element can be seen within the browsers window. It actually isn't testing that. The "Verify if Visible" step assumes the element exists somewhere in the browsers DOM (but could be hidden underneath another element or scrolled out of view). Test Studio is checking the visibility state of the element which could be set via CSS and a class name. It's looking for an attribute like "DISPLAY: NONE". If this is present the element is not visible and the browser won't try to paint it. If this attribute is not present the element is visible and the browser will try to paint at at the appropriate time.
However if the element does not exist in the browsers DOM, Test Studio is unable to test the visibility property. Thus you are getting the error "Unable to locate element. Search failed!". It's sort of like asking "is the color of this car Red" when there is no car to look at. Test Studio is coming back and saying "What car?".
You most likely want to replace your "Verify If Visible" with a "Verify Element Exists" step.