Lo que estas haciendo no tiene sentido.
El Parallel esta pensado para ejecutar tareas en paralelo, pero lo que vos estas haciendo ahi es levantar 10000 tareas en paralelo que lo unico que hacen es tirarle Invoke() al UI Thread.
El UI thread es 1 solo y por lo tanto el unico thread que termina ejecutando tus 10000 tareas.
Podria mejorar si en vez de Invoke() usas BeginInvoke(), aunque el resultado final en terminos de experiencia de usuario es el mismo, ya que el UI thread va a dejar las 10000 tareas encoladas y devolverle el control al Parallel.For(), con lo cual el tiempo que tarda en ejecutar tu codigo va a ser menos, pero el tiempo total en poner los 10000 listboxitems va a ser el mismo.
Por otro lado, como estas usando winforms, que es un framework horriblemente viejo, deprecado y lento, tu codigo tarda mucho mas que lo que tardaria si estuvieras usando un UI framework moderno que soporte virtualizacion de la UI y aceleracion por hardware, como WPF.
Esto es a lo que me refiero:
http://www.youtube.com/watch?v=D3Y6DnFpHCA