I'm playing Throne of Bhaal right now.

Imoen has the Staff of the Magi and is wearing a Cloak of Non-Detection. I'm hoping this makes her a completely undetectable scout. I send her ahead invisible, detecting traps and discovering what enemies are up next.

I assume that the Cloak of Non-Detection makes it impossible for anyone to see through the invisibility with True Seeing, and I assume that the fact that the invisibility and non-detection come from items, they cannot be dispelled.

However, a lot of creatures seem to be targeting her anyway. Most recently it was a fire troll ambush. A few of the fire trolls started attacking Imoen. Since I didn't see how it started, I realized it could have been that they appeared right beside her and she acted on her own initiative and took a swipe. So I moved her a bit away and quickly re-equipped the Staff of the Magi to get the invisibility back up. I expected that by going in invisible again, the fire trolls would lose sight of her. But they didn't, they kept chasing her.

Before that, my group had several encounters with Yaga-Shura Mercenaries. They too seemed to be able to target Imoen, even though she was invisible and under non-detection.

I don't think I had this problem at all in Shadows of Amn- Imoen had the Staff of the Magi and Cloak of Non-Detection throughout Watchers Keep and Chapters 6 & 7, and was relatively safe unless she broke invisibility through spell-casting. (On the other hand, she wasn't scouting in Shadows of Amn, either- it took a while for it to occur to me what the combination of permanent invisibility, non-detection, and 95% Find Traps could do for me.)

Do some creatures just see through invisibility? Shouldn't creatures lose track of her when she becomes invisible again? (I've certainly faced assassin enemies with unlimited invisibility who could backstab and pop back into invisibility before I could even target them.) Am I missing something when it comes to how invisibility and non-detection work? Do the powerful Throne of Bhaal creatures just have AI scripts that ignore things like invisibility? Is Imoen "going rogue" as it were, by doing things pursuant to her AI, and I'm just missing it?

There are a variety of monsters that can see through invisibility even with the cloak, usually either quest-related guys, liches, dragons, or major bosses. There's a script-based effect that makes certain NPCs essentially ignore invisibility altogether. Also, the Cloak of Non-Detection... well... it doesn't always work exactly like it seems it should. However, it OUGHT to work with the Staff of the Magi even if it doesn't work with some of the other spells. Its behavior seemed to change with ToB, which may be the source of your issue.

Note that enemies can often hear you even if they can't see you, but they shouldn't be able to attack you, though mages that hear you will often cast a detection spell of some sort. Honestly it sounds like more of a bug, because I've used the Staff of the Magi in ToB before (without the Cloak, usually) and it generally works fine. It's also entirely possible that Imoen is somehow breaking her own invisibility. You should be able to tell whether or not she's actually hidden, and re-equipping the staff should cause any enemies pursuing her to pause for a moment at the very least.

What I have found after playing a little more were that there were some creatures that were immediately spotting her despite the invisibility, and chasing her despite attempts to re-equip the staff to re-establish invisibility. Fell Cats, Fire Salamanders, and Flaming Skulls all ignored the invisibility completely.

The other two creatures we kept meeting- Burning Men and Fire Giants- acted as expected, not noticing her at all.

Kuo Toa spot a thief that's succesfully hidden, so I found out today...

I think it's just the Kuo-Toa Monitors who see through stealth/invisibility, but I don't remember exactly. I did not think to test a non-detection with them.

Fell Cats and Flaming Skulls have a script-based immunity to invisibility, so they will see right through it. Kuo-Toa are affected by invisibility normally, but they will follow anyone they can hear and they can all cast True Sight so it will get immediately dispelled.

Fire Salamanders can't see through invisibility, but they have a "Group Sight" script that allows them to follow you as long as anyone NEAR them can see you. I'm not sure whether this will let them attack you or not, though. Try killing the other guys in the group first and then see how the salamanders react to you.

I never use the non-detection spell but am a great fan of the cloak of non-detection for my thieves. However, this party of mine in the Underdark (my first time ever that far into the game), doesn't have such a cloak, so I didn't test either.

Well thanks, that's some interesting information as to what is going on. Hopefully I don't keep running into too many creatures who can pierce the invisibility/non-detection combination, I was just getting used to having a scout who could detect traps too.

Dragons see through invisibility. Perhaps other creatures smell or hear her. From a RP perspective, I reckon you can't effectively hide in shadows or be invisible vs. canine creatures (wolves, werewolves, gnolls, etc) due to their strong sense of smell. Perhaps something like that is what's going on with the fire trolls, fell cats & fire skulls; they sense Immy's heat despite the SotM & cloak you've equipped her with.

I believe even ghouls & ghasts have a strong sense of smell, regarding living (demi)human flesh.

cloak of non-detection doesn't work that way. It only works for characters using "hide/move silently". It does not apply to magical invisibility.

Didn't know that (but then, I use hide/move silent a lot more often then magical invisibility).
Does the spell 'Non-detection' protect against dispelling magical invisibility?

I don't remember. The only invisibility "trick" I would use was (improved) invisibility + spell immunity:divination. I remember trying the cloak a few times, getting frustrated, and then searching around for an answer.

I'm tempted to say the spell "non-detection" only works against "detect invisibility", but I might as well be guessing.

I took a look at the spell descriptions. Non-Detection will protect against "divination spells such as Clairaudience, Clairvoyance, Locate Object, ESP, and detect spells including Invisibility Purge." So that's good, and helps an Invisible character.

True Seeing is a divination spell, but however when reading the spell description, it specifically cancels Non-Detection.

Dispels generally don't dispel effects granted by items. The next time I play it shouldn't take me too long to run into another True Seeing wizard to test it.

Divination spells such as Oracle and Detect Illusion also apparently aren't divination spells "such as Clairaudience, Clairvoyance ..." etc., according to the spell descriptions. (Neither is Detect Illusion a "detect spell" for the purposes of Non-Detection.)

There are plenty of opponents who are true-seeing wizards and clerics, but I don't recall in any of the Baldur's Gate games that opponent has ever cast a spell on the list of spells Non-Detection guards against. Wow, what a disappointment.

Yeah, I only used the cloak of non-detection for a thief, and the spell never. I think you'll bump into some of the spells you mentioned as absent in BG1 if you use SCS1 w/ tutu.

In BG2, I did tweak my familiar (cat) to get a permanent non-detection effect, plus boosted hide/move silently. That was pretty dope. Enemy mages could not find the cat, and it could scout for me. I don't think I saved the CRE file, though I should go and look for it.
(and this worked against true-seeing IIRC)