So... wait until there are more foreigners there.
Or wait until your target is the foreigner.
Or until there are people from several different realms there.
Or until a well-known infiltrator is also in the region.
If you set yourself up as the only logical culprit, then you deserve to be the only one everyone suspects.
This, I had a infil character go unnoticed for more then a year by being very selective of my targets and my risks. Invisibility was always more useful for actually getting to your target region unnoticed then for plausible deniability at any rate.