Generics aren't an issue here. In all Java versions the way to go with the existing API is to use a Map with a collection (list, set) as its values.
If you want an easier interface, check out Apache Commons Collections or Google Guava - both have a multi map. However, Google Guava isn't an option for you as it's written using generics, and needs to be heavily modified to get working in Java 1.2. You should theoretically be able to recompile Apache Commons Collections using a Java 1.2 compiler, as it doesn't use generics (yet).