Hi mattc,
Welcome from a fellow CCIE! (bet you never expected that hehehe) I wouldn't be too concerned about the permit - it will get sorted out for you. I doubt your CV is landing in the bin because of it.
Now about the Basel thing. I guess you use jobserve already - but for a long while (as far as contract work went) there was nothing in Zurich and everything seemed to be in Basel. Then of course there are always things coming up in Bern for a company which starts with S.
In my own case I couldn't be bothered commuting to Basel each day (i'm lazy like that) so knocked them all back.
I am interested in what you might have to tell about the Zurich contract situation for CCIE's however, so send me a PM and we can chat in a bit more detail
Also, have you done your recerts lately? I may have a few tips for you there...