We have three foreign CFIs at my school (not EU) and I'm aware of others at neighboring schools. I don't doubt that if you started applying for CFI jobs during your training you could find a position before your M-1 expired. If I were in your position, I'd probably find a good smaller school where you could get to know the management and staff. They may be a little more understanding of your situation. The big pilot mills do hire their CFI trainees, but they can also be impersonal. Big school pay is also pretty low.