private void FindAllPages(List<ContentReference> list, ContentReference parentPage)
{
    var loader = ServiceLocator.Current.GetInstance<IContentLoader>();
    var children = loader.GetChildren<PageData>(parentPage);

    children.ForEach(pg =>
                     {
                         if (pg is ISampleInterface)
                         {
                             list.Add(pg.ContentLink);
                         }

                         FindAllPages(list, pg.ContentLink);
                     });
}

and

var list = new List<ContentReference>();
FindAllPages(list, ContentReference.StartPage);

An alternative soultion could be to first iterate over all ContentTypes returned from IContentTypeRepository.List and get those contentTypes where ModelType is assignable to the interface.

Then for each ot the content types found above call IContentModelUsage.ListContentOfContentType

Note that both my suggestion and Valdis suggestion (which also have the consequence that it will load up all pages to the cache) might take a considerable time to execute (especially for large sites). So if it is acceptable for the customer you should consider caching the result and then perhaps have a background timer or scheduled job that periodically updates the cached result.

Valdis recursive search works, but it does take some time to execute, guess I'll have to cache it :)

Nobody said it will come at no cost :)