Pelos seu conceito os meus testes deveriam ser o contrário:
[zillertal:~]$ java Test
Cast= 91
toString= 96
[zillertal:~]$ java Test
Cast= 98
toString= 87
[zillertal:~]$ java Test
Cast= 92
toString= 97
[zillertal:~]$ java Test
Cast= 96
toString= 87
[zillertal:~]$ java Test
Cast= 92
toString= 96
[zillertal:~]$ java Test
Cast= 102
toString= 88
[zillertal:~]$ java Test
Cast= 99
toString= 88
[zillertal:~]$ java Test
Cast= 96
toString= 86
[zillertal:~]$ java Test
Cast= 97
toString= 87
[zillertal:~]$ java Test
Cast= 87
toString= 87
[zillertal:~]$
Ou seja: micro-testes não provam nada. Melhor seria ter as operações feitas por cada trecho de código esperado. Mas nós podemos ver o que acontece pelos bytecodes usando o javap. Segue um trecho ( o javap completo está em anexo ):
/* Do primeiro for */
43: iconst_0
44: istore 6
46: iload 6
48: ldc #12; //int 10000000
50: if_icmpge 69
53: aload_1
54: aload_2
55: invokevirtual #13; //Method java/util/HashMap.get:(Ljava/lang/Object;)Ljava/lang/Object;
58: checkcast #14; //class java/lang/String
61: astore 7
63: iinc 6, 1
66: goto 46
/* Do segundo for*/
104: iconst_0
105: istore 6
107: iload 6
109: ldc #12; //int 10000000
111: if_icmpge 130
114: aload_1
115: aload_2
116: invokevirtual #13; //Method java/util/HashMap.get:(Ljava/lang/Object;)Ljava/lang/Object;
119: invokevirtual #23; //Method java/lang/Object.toString:()Ljava/lang/String;
122: astore 7
124: iinc 6, 1
127: goto 107
Ou seja: eles fazem o mesmo número de operações, o toString não tem que verificar o tipo pois ele pega o método herdado de java.lang.Object ( que por coincidência o objeto no Map é do tipo String ). Então é razoávelmente sem fundamento falar que um é mais rápido do que outro sem provas mais concretas.
Até!