As a belated ending to this episode 11 years ago, my NEXUS application was successful in 2009. I applied for my renewal (third NEXUS card) last week and despite no new applications or interviews being done due to Covid at the moment, my application was electronically cleared within 48 hours. I now travel around 150-170k miles per year and since this episode I have never had any issues at MSP (or any other port of entry) again. Go NEXUS!