This work evaluates the effects of using non-conforming fly ash (Nc-FA) generated in a thermoelectric power plant as filler material for mortars made with natural sand (NA) and recycled sand from masonry waste (FRMA). The incorporation of powdered recycled masonry filler (R-MF) is also tested as an alternative to siliceous filler (Si-F). Three families of mortars were designed to study: the effect of replacing Si-F with Nc-FA on mortars made with NA; the effect of replacing Si-F with Nc-FA on mortars made with 50% of NA and 50% of FRMA; and the effect of replacing Si-F with R-MF on mortars made with NA and FRMA. Replacing Si-F with Nc-FA is a viable alternative that increases the mechanical strength, the workability and durability properties and decreases the shrinkage. The use of FRMA and Nc-FA improved the mechanical strength of mortars, and it slightly increased the shrinkage. The replacement of Si-F with R-MF on mortars made with FRMA is not a good alternative, because it has a negative impact on all of the properties tested. This work can help both to reduce cement and natural resources’ consumption and to increase the recycling rate of Nc-FA and FRMA.