Looking over the matrix rules there are three ways to apply a mark, get invite, Brute Force and Hack on the Fly. If you are using Hack on the Fly you make an opposed test and if you are successful you can apply 1 or more Marks on the target. From reading the Matrix Perception action it seems like anything that is doing a Matrix Perception action (program your commlink/cyberdeck to run it on continuous action with a dice pool of DevRatingx2?) and getting 2 hits will let you know that you are marked (one to know that there is something out there and the second to actually get the mark count).

Is it really that easy for a host or icon with an active spider or Patrol IC to determine that his system has some unauthorized marks on it?

Yes, it is that easy.

Even the best security is not omnipresent, though. They might not be checking that particular icon until you have finished your hacking, which seems to usually happen in a comparatively narrow time frame.

Nope. It's that easy to know you have marks, but not if they are unauthorized. The rules are a bit unclear on legal vs illegal marks, but it seems like you can't tell with a simple matrix perception test. Now if it's your personal cyberdeck, and it's mark count jumps for no reason, you can get suspicious... but a host system's active marks will likely fluctuate a lot. Remember that any time a system reboots or is turned off, the marks it's user has placed vanish, so legitimate mark counts will change all the time on large systems.

To be even more specific: There is no such thing as an "unauthorized" mark, as the mark IS the authorization!

Raben-AAS -- I know what you mean by that sentence, but given that hackers can mark things that don't want to be marked, that statement is an awful lot like holding up a gun and saying "I don't need a badge, THIS is my badge."

I see it more like: "Of course I'm authorized to be in here, the sign on the door says Authorized Personnel Only and I'm in here, aren't I?"

Well thats where the balance between the two factors comes in. If the Host or Device is expecting Marks then it may not be concerned, if it isn't (IE Cyberdeck, single user server) then it might be. Also Marks are distinctive to the Persona that places them, which means a more suspicious system may notice that a Mark doesn't tally with the list of "anticipated Marks".

So a publically accessible Host won't look twice at a random Mark. A closed but massively accessed Host again is unlikely to take note of a Mark unless it's paranoid enough to check a database of regular or anticipated Marks. The smaller the user base the more it's likely to attract attention. On a closed and limited access host it'll either flag an unexpected Mark or run it against a database.