Here is the logic. This is based off of a recreation of the game's code in C discovered by aphid, in the other answer to this question. As they said, the relevant code is mainly in /src/renewable_hidden_items.c. Obviously, this information is only valid if the people behind this project did a good job at recreating the game's code, but presumably they wouldn't have just made up an entire algorithm based on nothing.
Certain, but not all, of the hidden items in the game are marked as "renewable". Each renewable item is marked as either "common", "uncommon", or "rare" (or several of the above, see below).
All renewable hidden items are absent when the game starts.
Every time you take a step, a step counter increments. When it reaches 1500, you enter what we'll call "respawn mode". For reference, Celadon city is about 50 tiles across (west to east).
When in respawn mode, if you enter a zone that contains renewable hidden items, a global renewable item refresh is triggered. Your step counter is then reset to zero and you leave respawn mode.
The "global renewable item refresh" algorithm is:
Despawn all renewable hidden items in the entire game.
For each zone in the game that contains renewable items, do the following.
Generate a uniform random value from 0 to 99, inclusive.
If the value is from 90 to 99, respawn all rare items in this zone.
If the value is from 60 to 89, respawn all uncommon items in this zone.
Otherwise, respawn all common items in this zone.
A few points of emphasis, so there's no ambiguity:
Yes, when you enter a zone with renewable items, it triggers a global refresh across the entire game, not just that zone.
The refresh is only triggered when you enter a zone with renewable hidden items, not at any zone transition. Other zone transitions do not cause you to leave respawn mode and do not reset your step counter.
The random values generated per zone during a refresh are all independent.
However, the respawning of the items within a single zone are not, since they happen in batches: either all the rares, or all the uncommons, or all the commons.
It really is "all the rares", not "all the rares and anything less rare". Getting a number above 90 does not respawn the uncommons or the commons. However, in some zones items are simultaneously of several rarity levels, to basically emulate this "rare and under" behavior.
During a refresh, all items are despawned. This means once one spawns, if you don't go back and get it before the next respawn, there's a good chance it'll be gone by the time you get there.
Finally, the list of all renewable items in the game:
Zone
Item(s)
Rarity
Route 20
Stardust
Uncommon
Route 21 (north)
Pearl
Uncommon
Underground Path (Routes 5-6)
Potion, Antidote, Paralyze Heal, Awakening, Burn Heal, Ice Heal
Uncommon
Ether
Rare
Underground Path (Routes 7-8)
Potion, Antidote, Paralyze Heal, Awakening, Burn Heal, Ice Heal
Uncommon
Mount Moon (B1)
Tiny Mushroom x3
Uncommon
Tiny Mushroom x3 (the same ones), Big Mushroom x3
Rare
Tanoby Ruins
Heart Scale x4
Rare
Berry Forest
Razz, Nanab, Chesto, Pecha and Rawst berries
Common
Bluk, Wepear, Oran, Cheri, Aspear, Persim and Pinap berries
Uncommon
All uncommon berries, Lum berry
Rare
Treasure Beach
Ultra Ball x2
Common
All common, Stardust x2, Pearl x2
Uncommon
All common, Star Piece, Big Pearl
Rare
Bond Bridge
Pearl, Stardust
Uncommon
Four Island
Ultra Ball
Common
Pearl
Uncommon
Memorial Pillar
Big Pearl
Rare
Resort Gorgeous
Stardust x2
Uncommon
Nest Ball, Star Piece
Rare
Outcast Island
Net ball, Star Piece
Rare
Green Path
Ultra Ball
Common
Trainer Tower
Pearl
Uncommon
Big Pearl
Rare
Note that because Berry Forest and Treasure Beach both have items of all three rarity levels, you're actually guaranteed to get items from them every 1500 steps. Also worth pointing out is the renewable Ether in the Underground Passage - I always thought Ethers were a finite resource in these games, but technically not (you just have to walk 15 thousand steps on average to get one).