This problem can be easily solved if you are ready to pass around "type" tokens i.e. Class instances to methods. Let's say you want to create a generic "doSomething" method as mentioned in your first post. The generic version would look something along the lines of:
public <T> T doSomething(Object obj, Class<T> klass) {
T someObject = klass.cast(map.get(obj));
if(someObject == null) throw new SomeException();
return someObject;
}
Also, when you instantiate any "generic" object using reflection, all the bets are off (given that you have used introspection and not regular constructs which are subject to compile time checks) and hence it might be a bit misleading to say that you created a "Map<String, String>" because under the hood, it's just a Map instance (given that generics are implemented using type erasure).