Veamos,es un tema bastante más complejo de lo que parece en un principio.En El Anillo de Morgoth(uno de los libros de La Historia de la Tierra Media) Tolkien divaga con cuatro posibles orígenes:
-El más común,que proceden de los elfos capturados por Melkor,fueron transformados por él y fueron corrompidos hasta llegar a lo que todos conocemos.
-Proceden de humanos seducidos por Melkor y adaptados a sus necesidades,en cierta manera transformados también.
-Son animales y por tanto no tienen fea(alma,espíritu)
-Eran Maiar seducidos por Melkor(al menos los más poderosos).

Cada cual que elija,yo me quedo con lo de los elfos.
No recuerdo que se diga en ningún sitio que sean inmortales.Si son corrupciones de los elfos dudo que posean tal capacidad.

¿A dónde van cuando mueren?......si son corrupciones de elfos,y por lo tanto su alma es élfica tienen dos opicones:
-Si escuchan el llamamiento de Mandos van a las Estancias de Mandos y tras un periodo de tiempo(supongo) muy largo pueden obtener el perdón.
-Si no escuchan el llamamiento de Mandos se convierten en almas perdidas que vagarían por el mundo sufriendo constantemente.

Recordar que Melkor no puede aniquilar ningún espíritu,con lo cual cabe la posibilidad de que si los orcos proceden de los elfos conserven su espíritu original.
Saludos.