Here's a piece of valgrind log from bug #515744
As you can see, Evolution uses this function very often, and it calls properly 
gtk_icon_info_free (icon_info); (see code below) thus it should not leak from evo's point of view. Can you check it, please?

==3667== 1,614,176 bytes in 68,025 blocks are still reachable in loss record 316 of 318
==3667==    at 0x4022825: malloc (in /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so)
==3667==    by 0x56C07FC: g_malloc (gmem.c:131)
==3667==    by 0x56D8FE8: g_strdup (gstrfuncs.c:92)
==3667==    by 0x4E32196: insert_theme (gtkicontheme.c:2521)
==3667==    by 0x4E324CC: insert_theme (gtkicontheme.c:995)
==3667==    by 0x4E324CC: insert_theme (gtkicontheme.c:995)
==3667==    by 0x4E3352E: ensure_valid_themes (gtkicontheme.c:1043)
==3667==    by 0x4E33C60: choose_icon (gtkicontheme.c:1253)
==3667==    by 0x4E34F1D: gtk_icon_theme_lookup_icon (gtkicontheme.c:1401)
==3667==    by 0x4167AF3: load_icon (e-icon-factory.c:101)
==3667==    by 0x4168163: e_icon_factory_get_icon (e-icon-factory.c:340)
==3667==    by 0x805148F: query_components (e-component-registry.c:215)

Evolution's code in question is:
		GtkIconInfo *icon_info;

		icon_info = gtk_icon_theme_lookup_icon (
			icon_theme, icon_name, size, 0);
		if (icon_info != NULL) {
			filename = g_strdup (
				gtk_icon_info_get_filename (icon_info));
			gtk_icon_info_free (icon_info);
		}