I'm wondering if OBSE has the capability of scanning a cell on load, identifying particular creatures/NPC types, recording their position, removing/disabling them and then replacing them with a different creature/NPC. And it has to be done fast enough to not totally mess with the Player.

Off hand, these are the requirements I foresee, in no particular order.

Two arrays. A larger one generated from a text INI file, and a smaller backup one generated by the player in game by physically selecting creatures/NPCs to be removed.
A set of commands to walk through all the creature/NPCs in the players active cells and check their FormID against the arrays.
A non-playable token to mark already scanned creatures/NPCs
A script to check the inventories of creatures/NPCs chosen for removal in an attempt to see if particular items in their inventory need to be moved to the replacement creature (this is likely to be buggy as hell, so)
A community generated exception list of creatures/NPCs that can't be removed without breaking quests. A separate ESP file would have to be made to fix these issues.
Commands to locate the position of the chosen creatures/NPCs, and their aggression/disposition/combat status toward the player.
Clean way of disposing of the chosen creature/NPC
Script to replace the chosen creature/NPC with the matching one from the arrays, add necessary inventory, modify position/aggression/disposition/combat status to match removed creature/NPC.
Possibly a way to permanently replace levelled/creature/NPC lists of spawn points with new ones in order to avoid having to repeat process on return to same cell?

What do we think? Possible? Other needed elements?

I'd imagine it could be made to work well enough if you never teleported into a cell. If you walked everywhere and never used a door, the script would have time to do its thing. I just can't see it being quick enough to replace a creature standing next to the door you just came through without it being obvious what's happening.

I also can't see any way to pre-scan a cell you're going into, so that it's all happened before you arrive.

Yeah....outside is fine, I think, because Oblivion loads the cells at a distance.

Inside, in a new cell or using a teleport I can only think of one option off-hand. Use ScreenEffects to blank the screen, shut off all AI, do the replace routine, and then turn on the AI and the screen simultaneously. Hopefully it would appear as a longer load screen effect.

Not really.
Whatever you are going to use to trigger your script, will either trigger it on time or too late.

If it is too late and the switch will be noticeable, it will be too late for anything else you may devise (including black screens and such)

If it is on time, then there is no need for trying to cover it. Just replace them and you will be done.

What you have to worry about is how to trigger the script as soon as the PC enters the cell.
I think a token would work.