A few days ago I was playing with "to hit rolls" feedback on and I noticed that a large amount of the time while trying to backstab something, I become visible without a roll to hit or miss ever being made.

A few ideas come to mind:

1) Are you backstabbing with a 2-handed weapon? That won't work. (Except staves, which will)
2) Are you using a very slow weapon? You only get a small window between initiating the backstab and stealth fully wearing off, so a slow weapon could possibly - depending on your timing - not swing until your stealth has dropped
3) Are you actually in stealth when you start the backstab, or does the thing you're backstabbing detect you, cancelling your stealth?

That's all that comes to mind. If you are dual or multi and wearing armor that thieves aren't especially well suited for, that might put a big hit on your effective stealth, which could have you dropping out of stealth before you actually swing. To test your timing, try setting autopause to trigger every round, and start the new round stealthed (or, better, invisible) and launch the backstab then.

Except the Staff of the Magi, which will not.

(My understanding is that backstab works with any melee weapon a single class Thief can equip, as well as any melee weapon created by a spell (like the Iron Giant Shapechange form's claws).

Well, the Staff of the Magi does give the wielder free invisibility. Wouldn't that be nice for backstabbing?

Also, Yoshimo can easily kill the Shadows of Amn final boss in one hit if shapechanged into an Iron Giant. It is an exercise to the reader to figure out how to accomplish this (or just watch a speedrun).

I think I was just using something basic like a longsword +1. It was mostly near the beginning of the game. And I was playing as a pure thief (bounty hunter) so I'm sure I couldn't use two handed weapons. Yes, I was hidden when I clicked on the enemy and I don't think anything in Irenicus's dungeon has detect invisibility. I don't know much about how weapon speed effects when the first hit of a fight will land. I know usually the roll will be made on the second animated swing the character makes, with it sometimes being the first or third, maybe even the fourth. Usually when I leave the shadows due to a failed upkeep roll, it can take a round or two for more for me to actually become visible, but when attacking it seems to wear off much faster.

^Can longswords backstab? I thought they weren't a natural thief weapon - shortswords are ok - try one of those. Yoshimo? er... (Do you mean Jan?)

I thought Staff of the Magi could backstab (and its invisibility on equip thereby making it cheesy) - is this something that changed in the EE?

Longswords can backstab. Since I was playing a pure thief class, any melee weapon the game would allow me to equip would be able to backstab (before getting Use Any Item anyway).

I actually do mean Yoshimo. Of course, this means using the item swap glitch to get him to cast Shapechange or Limited Wish from a scroll (and then killing him so the effect doesn't go away), and then having him polymorph teleport over to the gate to the Underdark, allowing you to skip most of Spellhold.

Speedruns of Infinity Engine games are completely different from normal playthroughs.

(Of course, there is nothing preventing Jan from accomplishing this feat especially since he doesn't have to item swap or polymorph teleport to accomplish this.)\