I'm playing Arena for the first time and I have failed the last two quests to kill XXX at YYY because I cannot find the monsters, despite searching the entire map. I've found the dungeon where the beast resides (assuming the red square indicates the location), but searching and searching and searching...I'm just about to put this game away, so if anyone can give me some advice, I would much appreciate it.
- eep!

The red square is the indicator for the level above you, and if you're on the first floor that would be the exit. I'm pretty sure most dungeons in Arena, if not all, have multiple levels. The entrance to the lower level is indicated by a blue square.

If I were you, I'd go about three to four levels down, search the entire level, and kill everything you see. If you still don't get any message saying you've killed the creature then I don't know what to tell you.

I'd be of more help if I'd play the game once in awhile. Today was the first day I've turned it on in a few months, and it was just to see how well it worked on my Eee PC.

Eepcat, I'm afraid that your post didn't add up to me.

Red squares indicate doorways on city and dungeon maps. Outside the city walls you can find squares that might be called red, but I would describe more as an orange; those are never quest dungeons. They're just random dungeons. Perhaps you took the directions you were given literally, and left the city heading in the direction you were told.

Anyway, Arena doesn't work like MW or OB in that you can get some directions and use them head off in some direction. Rather, the wilderness is random and specific to the outside of each city, and the cities and wildernesses are non-contiguous. (It might help you to think of each city as being on its own plane a la MW's Mournhold or OB's Shivering Isles.)

If you're given a quest, here are the steps you take:

1. Check your journal (press the L as in "log" key) for the province and location your quest should take place. If there is no province, it's safe to assume it's in your current province.
2. Use the fast-travel map (Shift-M) to travel to the location you have been directed to.
3. In that location, find your quest item. It's usually (possibly always) on the lowest level of the dungeon; just keep looking for blue dots that show the way down. Sometimes the game tells you when you're getting close.

You can't go wrong with those steps.

Dr. Memory - thank you very much...I made a very bad assumption. I started walking west (in the direction I was told) until I came across a building that had a red square in it per the map. I mistakenly identified this as a marker for my destination, rather than what it actually is....a frickin' door! Luckily, I can go back a save and salvage the current quest by actually finding the real location.
Thanks again,
- eep!

You're welcome. Also note that blowing a quest in Arena has no lasting implications, so if you blew one, it doesn't matter, just get another.