Why are the hidden items in Fire Red/Leaf Green sometimes absent?

Someone has done part of the research necessary to answer this question already.

Take a look at the topic over here.

It appears that something in the game is dynamically affecting the flags for some hidden items (as there are no explicit references to these memory locations in the machine code for the game). Somewhere in the memory of the game is a list of boolean values that keeps track of which items currently are still on the map (see the topic above for details). These values are supposed to be set at 0x01 and remain so until the player picks up the item.

Suggestions of clearing the S.S. Anne or etc. are likely just incorrect; it's something else the user did that caused the items to appear.

Edit: Found the solution

It's random.

A lot of the time, people try and appear to succeed at finding patterns in things that are (pseudo)random. Instead, the game does the following: after the internal step counter reaches at least 1,500 steps a flag is set. If a new location is entered afterwards, items in this location are respawned with a fixed probability.

This means that if you walk through the game in a very efficient pattern, you will find fewer hidden items (as there will be a lower amount of spawns).

Look at the repository (a project that attempts to re-create code that compiles into the mainline pokemon games), specifically in /src/renewable_hidden_items.c,

{
    .mapGroup = MAP_GROUP(UNDERGROUND_PATH_EAST_WEST_TUNNEL),
    .mapNum = MAP_NUM(UNDERGROUND_PATH_EAST_WEST_TUNNEL),
    .rare = {
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_ETHER,
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF
    },
    .uncommon = {
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_POTION,
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_ANTIDOTE,
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_PARALYZE_HEAL,
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_AWAKENING,
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_BURN_HEAL,
        HIDDEN_ITEM_UNDERGROUND_PATH_EAST_WEST_TUNNEL_ICE_HEAL,
        0xFF,
        0xFF
    },
    .common = {
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF,
        0xFF
    }
},

Note: The North-South tunnel has an identical drop table.

There are 6 independent 70% chances of not getting the uncommon items to appear if the step counter ticked over before entering the underground tunnel. There's also one rare item that won't appear 90% of the time.

Thus there's a significant chance of p = .1058841 (10.6%) that you won't find anything. Try walking around within one of the routes connected to the underground for at least 1,500 steps, then re-entering it. See if the items can now be found.