First problem: Do (if yes: how) I know if the target has the ability to cast spells or not? Should I just subtract 1d6 sneak damage vs. anyone who could possibly be a cleric?
You do not know, unless you use something like detect magic (debatable), arcane sight, or some other effect. You may be able to guess at their class, however (if they're wearing robes it may be worth a shot), or wait till they use a spell.
Second problem: How the heck should I know what spells or even spell levels my enemy has? I only see solutions via Knowledge (local), Sense Motive (CR/2=highest spell slot) or targeting a previously cast spell.
A spellthief can choose which spell to steal; otherwise, the DM determines the stolen spell randomly. If a spellthief tries to steal a spell that isn't available, the stolen spell (or spell slot) is determined randomly from among those that the target has available.
So, you can hazard a guess if there's a particular spell you really want to steal or really don't want cast against you, or you can target a spell the fellow has already cast. Trying to guess won't hurt, because if you're wrong you'll still steal something random, and if you don't specify you'll also steal something random. You may be able to talk your DM into letting you specify a spell level, or descriptor, or something that could still be handy (if you're level 8, then you may want to specify stealing a 4th or 5th level spell, since that's probably the highest spell level your enemy can cast) - but of course that is up to your DM. At worst, you can always get something random, which may or may not be helpful. (Also remember that you can use things like Knowledge (local), Gather Information, and divination spells if you have prep time before the battle with the BBEG.)
Third problem: Assuming I'm Spellthief 1/Wizard 10, I can steal 5th level spells but can only hold one 1st lvl spell or two lvl-0-spells?
That's debatable... I think RAW you're correct - Master Spellthief lets you steal higher level spells but not store them for later use the way a full-classed Spellthief can. It's still a handy side effect, at the least. You may also be able to talk your DM into letting your levels stack for the purpose of storing spells as well as stealing them - it's entirely possible that was an oversight by those who wrote that feat (it's not covered in CAd or CSc errata, but not every oversight is caught in time for errata...).
Fourth problem: Assuming I managed to steal a useful spell I could cast on my own, could I cast it now even if I'm not Spellthief 4?
There's a few issues here.
1. When a spelltheif steals a spell, he can cast that spell as if it were cast by the fellow he stole it from; that's explained in the bulk of the steal spell ability description. Assuming you can hold the spell at all (see your third problem), then you can also cast it. The bit you quoted doesn't have anything to do with being able to cast the spell you stole.
2. The ability you quoted allows you to use the spell you stole to power one of your spellthief class spells. This isn't a separate facet of the steal spell ability (it's not mentioned on the class's summary chart), it's just that spellthieves don't gain the ability to cast their own spells until level 4 (look at their spell progression). Since you only have 1 level of Spellthief, and since Master Spellthief stacks caster levels but not spell progression, you can't cast any Spellthief spells, and so you can't use the spells you steal to power extra castings of Spellthief spells (you don't know any Spellthief spells to cast). If you can talk your DM into letting Master Spellthief also stack spells per day and spells known, then you could indeed cast Spellthief spells with the energy from your stolen spells, yes.
3. You didn't mention it, but just to be clear, you cannot use the stolen spell energy to cast a Wizard spell either; the Steal Spell description specifically limits it to casting Spellthief spells and not spells from other classes, and nothing from Master Spellthief counteracts that. Again, you may be able to convince your DM otherwise, but RAW it doesn't work that way.
