It's interesting to note that in .NET's case, work on generics started as a research project back in 1999, long before the first .NET 1.0 beta had even been published. On the Java frontier, JSR 14 "Adding Generics to the JavaTM Programming Language" was initiated in 1999 as well (actually Java generics are based on the even older project Pizza/GJ). Six years in the making, in both cases. Amazing.
More on generics in Java 5 and .NET 2.0 can be found in this transcript of an interview with Anders Hejlsberg (talking with Bill Venners and Bruce Eckel) and Gilad Bracha's Java generics tutorial.