If we define "illegal position" as a position that cannot happen in a game using legal moves, I think most difficult to spot would be positions that look normal, but are impossible to achieve.

    [FEN "2k1rr2/pbpq2b1/1p1p1np1/nB1Pp2p/2P1Pp2/2N2NP1/PPQB1PP1/2KR3R w KQkq - 0 1"]

For example this position looks legal, but indeed there is no way how this position could happen in real game - all 16 black pieces are on the board and yet white have doubled pawn. There could be lots of such positions in which none of the rules you mentioned are broken and yet, the positions are impossible to achieve, for example: 

        [FEN "4rrk1/ppp1bppp/2npbn2/1B6/3NP1q1/1P1Q1N2/P1P2PPP/1K1RR1B1 w Qq - 0 0"]

There is no way white bishop could get to g1

        [FEN "2krr3/pppbppbp/2n1pnp1/1B2q3/4P3/2N1QB2/PPP1NPPP/R4RK1 w KQkq - 0 0"]

There is no way how white could get two white-square bishops. Yes  they could promote a pawn theoretically, but the only square where this would be possible is d8 and this square is black. So had they done so the bishop would be black-squared (not mentioning the fact that with two pawns on c7 and e7 there is no way how bishop could get away from there.

        [FEN "6k1/p1p1np1p/1p4p1/3Kqr2/8/BQP3P1/P4P1P/1R6 w - - 0 0"]

What was the last move? etc.