I have a Huawei E220, which works fine with that kernel, using wvdial
to connect. It is one of the "hockey puck" type dongles, so a little less convenient than the "stick" type.
I have mine through a contract with Vodafone, though I suppose if you think you're likely to want to change networks and unlocked one would make sense. There is a free utility
for Vodafone which is said to work with kernels newer than 2.6.17
and support Huawei E620, Huawei E220 and Option GlobeTrotter 3G+ EMEA. Not got around to trying it, though, so can't comment on it.
Not an answer to all your questions, but I hope that helps,