Redemption - Soulstone Part I - Rithnok's Soulstone
1. Head to North Qeynos and talk to Enic Ruklin, wanders near vf the Temple of Life. Say 'What happened?' and 'I will help you track down'.

Enic Ruklin sometimes wanders the zone
2. Next to East Freeport and the lower level dock (you should probably be invisible if you have too many run ins with the guards) and talk to Brunar Rankin (-200, -950). Hail him and receive 'An Iksar's note'. The note reveals four places you need to fish from.

Brunar Rankin went for a swim shortly after I hailed him
3. You need a fishing skill of over 100 to do the next steps, but fishing goes up relatively painlessly. Start fishing at the below locations and when you get the message 'As you reel in the dark fish's scale, you notice a large fish in the water ready to attack you' jump in the water and attack 'A Corrupted Koalindl'. They have around 4k HP, flurry, hit up to 500 at times, are unrootable and run when they get to 20%. If you chain stun and cast Supernal Cleansing you should win all the fights with at least 30% health left (at level 65+). All the Corrupted Koalindl have poor pathing (and Z-axis problems) which is a bad thing if you are chasing it, but a good thing if it is chasing you. They drop 'A Corrupted Koalindl's Heart'.
Finally another quest with the Minnows of Marr versus the Piranha!
Ocean of Tears
-Fish on the Sister island near the dock.
Overthere
-Head East along the coast. Half way between Nekexin Virulence and just West of the bay that turns North.
Gulf of Gunthak
-Swim South to the beach and start fishing on the Western side. When you get the message swim North and West to around (200, 100).
Nedaria's Landing
-From the wayfarers camp head straight to the water and start fishing. The fish ran East.
They are lore, but each is identified differently
4. Give 'Enic Ruklin' the four hearts to receive 'Seal of Enic'.
5. Head to Skyfire and find Dry Sapara at the gate to Veeshan's peak. Hail her with the Seal of Enic on you to spawn Rithnok to the North East.

Clear the mobs in front of Dry Sapara before you can safey hail
her

My guild made quick work of this Tormented Soul
6. Head out of the VP entrance and slightly left to the boulder to find Rithnok the Tormented. He is a level 68 Undead Drake, hits in the 800s, flurries, has high MR and proc's HT infrequently. One solid group should be able to finish him off relatively fast however I brought two and a half groups not knowing what to expect (read: massive overkill). Once Rithnok drops Rithnok's Soulstone, hand it to Dry Sapara and she will hand it back to you as a container. She wants you to collect Soulstone Shards.
7. Soulstone Shards a glowing blue orb graphic and are ground spawns in Omens of War.

Soulstone Shard in Noble's Causeway (facing South towards Dranik's
Scar)
Noble's Causeway (-900, -350)
-As you run towards Wall of Slaughter keep an eye peeled on the lower ledge area.
Dranik's Scar (1000, 100)
-As you head to Bloodfields, it's at the bottom of the large ramp between the two towers.
Bloodfields (450, 730)
-It's in a stone building under 'a noc darklurch' foot, as you head the Ruins of Dranik zoneout.
Ruins of Dranik (-500, 360)
-This is incredibly dangerous as a few mobs see invis, all mobs are yellow and red (at level 65) and they snare and stun. Invis Potions are a must if you are doing this without a caster and make sure you /consider everything to make sure it does not see you (read: indifferent). Go through the first canyon - hugging the left wall high, Head South west over the bridge to the south of the Bridgekeeper's area. Take a hard left South East and up the hill to an encampment area. You should be able to see the shard on the ground to the left, grab it (and probably aggro something that sees invis) and run like mad back to the zone in (Horses are not allowed).
Right before the combine
8. Combine the 4 soulstone shards in Rithnok's Soulstone. Results in: Rithnok's Soulstone.

Soulstone Number One of Four complete!