I used to get by in Soldier of Fortune II just fine on dialup. Q3-based games are generally easiest and if you find a good server, UT2k3/4 is fine also. 2-3 years, that's rough considering how far things have come....I remember when it took that long for mine, but now I finally have it.
Still not really 'recommended', although in BF1942 we have a guy in Poland on dialup who kicks some ass (although punkbuster keeps kicking him for high ping)