When you first enter the Keep of Tinraya you should make your way throughout the town, including outside the walls to find the Alien Beasts. I chose not to put them on the map, since they're all over the place, and tend to move around a lot. Assume that you'll run into Alien Beasts around every corner and in every room and that way any surprises will be pleasant ones.
Once you've killed as many of the Alien Beasts as possible make your way down to the southwest corner of town, using Move Mountains on cracked walls as necessary to enter rooms. When you reach the forge check around for the Justice Lance.
Now make your way up to the northeastern corner of town. In the inn is a room you can rest in, but doing so spawns the creation of more Alien Beasts throughout the town. Make your way out onto the walkway of the wall in this corner of town to find a lever. Pull the lever to open a portcullis in the northwest corner of town.
In the northwest corner of town, behind the Portcullis you raised is a supply cache with a few items, including some Blessed Missiles and a Blessed Large Shield.
Once you've explored the rest of the town go to the southeast corner. The room just to the east of the South Gate contains a Robe of the Magi which you probably want to scoop up.
Now go to the room in the far southeast corner. There's a large group of Pack Leaders in here, guarding a ladder down to under the Keep.
When you get down the ladder you'll find yourself in a warren of tunnels, once again with so many Alien Beasts that I chose not to list them all.
There's a secret passage in the northwest corner of the first room which leads to a boat. Using the boat will make it easier to navigate your way through the tunnels, but the tunnels themselves are a bit of a maze. I suggest exploring the tunnels fully, checking the ground frequently, since a couple sections contains potion-making herbs.
When you finally reach the northwest section of the tunnels you'll find yourself facing a building. Going west you need the key from the New Formello Murder quest.
The first room you enter in this building contains quite a few statues. Head south until you trigger the release of several Alien Beasts from a couple cells to the north. Kill the Alien Beasts and then explore the rest of this building. There's quite a few nice items lying around, and, in the far northwest corner, a crystal that will teach you some Vahnatai Lore.
Now make your way towards the southwestern corner of the map, through some tunnels, until you reach a door. Going through this door will put you face to face with Rentar-Ihrno. She'll transport you to a cell.
You have to wait in this cell for quite a while, but eventually a spirit will come along and give you a message before opening up the eastern wall of the cell to reveal a teleporter. You can only send one person through the teleporter, and you're going to have to fight a few times. Use your judgement as to who should go through.
Once you're through make your way east and then south until you re-enter the building, this time through a different door. There's only one path you can follow, so do so, killing any Vahnatai you come across.
As soon as you're able make your way to the eastern side of the building, and into a small meeting room with a control panel in the northwest corner of the room. This panel controls all the portcullis' in this area. I usually just set them all to open, but if you want to be cautious look carefully at the buttons. The layout on the control panel mirrors the layout of the portcullis' themselves. You want to get into the room just south of the meeting room.
Once you're in that room go towards the crystal at the end. Push the right button to release the rest of your party from their cell. Pushing the left button releases some Alien Beasts from their cell just to the north of yours.
Now that your party is reunited go back and open the doors. The room to the west of the cells contains a Vahnatai, and a crippled Alien Beast. Once you've dealt with them go through the locked door on the western side of the room. There's quite a few items in here, but the most important one is in the chest. It contains a key that you'll need to finish the game.
The double portcullis at the west end of the hallway blocks another hallway with a room to the north, also blocked by a portcullis. Through that door you'll find the Thirsting Blade.
Finally, head through the doors to the west which will take you back to the room where you first confronted Rentar-Ihrno. If you have the Thought Crystal from the Bunker in New Cotra, which you get if you say that you believe the Vahnatai are behind the monster plagues, Rentar will teleport out and take the Mind Crystals in this room with her, leaving a few Vahnatai Blademasters behind. If you don't have the Thought Crystal then the Mind Crystals will stay. You don't want to kill the Mind Crystals, since you won't receive the help of the person who's been giving you all the messages when you reach the Vahnatai Lands. If you have to fight the Crystals your best bet is to haste your entire party and sneak them across the room to the door you first entered from the tunnels.
If you can, there's a secret room in the northwest corner of the Mind Crystal room, but the items in there aren't anything too terrribly exciting anyway.
Once you're out of the room make your way north along the tunnel until you reach a ladder. This ladder leads up into the area of the Keep which was blocked by portcullis'.
Directly south of where you entered is a wheel which controls the portcullis to the east, but you can't use it unless you have the key from under the Keep.
The next four rooms, two north and two south, contain the spawning pools for the Alien Beasts. Use Dispel Barrier or Piercing Crystals to get through the barriers, and approach the brazier in the center of each room. When prompted to do so, tip the coals into the pools to destroy them.
Once you're done with the spawning pools use Dispel Barrier or a Piercing Crystal to get through the barrier at the west end of the hallway. Make your way to the center of the room, going around the walls to find yet another ladder.
Go down the ladder and follow the passage until you reach a large heavy door. You need the key you found in the building in the southwest section under the Keep to get through the door.
Once you're through the door go out the passage to the west and find yourself in the Vahntai Lands of Footracer Province.