This problem may have two reasons:
1. Your product is already presented in the other listing.
There's “Products Presented In Other Listings” functionality available in the Advanced Filter that allows you to show, or hide products presented in other M2E Listings.
Most probably it is set to Not Show, so products which are added to other listings are not shown in the search result.
To figure it out, click on the “Show Advanced Filter” button. In a drop-down list on the right, select “Show” and press Search button. Thus, the needed product will be displayed in the product list.
Read more information about Advanced Product Filter for Magento v1.x and Magento v2.x.
2. The product is not added to the Website associated with Listing Store View.
A website contains one or several Store Views. You need to choose the appropriate Website when adding a new Product. However, if the Store View is not associated with the particular Website, the product will not be displayed in the number of products available to add to the Listing. Thus, you have two solutions: