Remember, searching from Start Menu only searches indexed locations. By default, AppData is not indexed. Searching from Explorer searches the current location plus all its subfolders (also non-indexed locations). So, in order to search AppData, open Explorer and browse to AppData folder, then search.
Here's for instance a search for files whose name include string "Chrome" in my AppData folder (filename:Chrome). Search had non whatsoever problems: