Hej
jag är i exakt samma situation som dig. Jag har läst mig till olika lösningar, som jag tänkte prova.
En är att använda varmt vatten med maskindiskmedel (undrar om vanligt fungerar dock) och sedan gå med lavemangsborste (typ hård) och skrubba själva teglet.
En annan är att gå på med saltsyra (tänk på SIV regeln) men den versionen kan nog vara ganska farlig om man inte är aktsam.
Gnugga gnugga och mera gnugga, sedan ska det vara klart.
Som ytfinish kan man använda antingen klinkerolja eller någon form av lack, beroende på hur matt eller glansigt du vill att teglet ska vara.
Lycka till