If the map says you can't go a certain way, will this always happen if you manage to go that way?
In that particular case, yes (see above), but there are tons of places where 'solid' map walls hide passable secret passages. Once you find such a passage in the gameworld, that map wall will also have a small hole to indicate that passage. So, I'd suggest trying against solid walls in every direction - you never know what you'll find!
(Another thing that can change a 'solid' map wall is an earthquake event. The resulting hole in the map wall is going to be slightly wider than the secret passage hole.)