Assuming that people can walk 20 miles in a day there would need to be an average of 36.5 miles traversal between rooms to not fully explore 1000 rooms in 5 years. 20 miles a day with 365 days in a year for 5 years gets you 36500 miles traveled, split between 1000 rooms.
If you factor in backtracking, if your "maze" is a balanced binary tree with 1023 rooms, and you start at the root node, you'd need 2035 room traversals to fully explore every room. (I have no idea if this is the worst case for full graph traversal. Any graph theorists who can provide more insight) Since your explorers will travel 36500 miles in 5 years, the average traversal between rooms must be 17.9 miles.
This is assuming that people are just intending to visit every room. If they're searching for a specific room, 17.9 miles is the maximum distance that guarantees that they will find their goal within 5 years. Assuming that their goal is randomly located, it's likely that they'll find it in 2 and a half years.
Getting a bit nerd sniped by attempting to figure out what the worst graph and starting vertex would be. The shortest worst case minimum traversal is $n-1$ steps from any vertex on a Hamiltonian graph. The longest worst case minimum traversal I've discovered is the star graph, starting from the center vertex. I haven't proved it but I suspect that the star graph may have the longest worst case minimum traversal of any graph.
I haven't determined the formula for the worst case minimum traversal for a binary tree, but the worst starting vertex is the root. The length of the worst case minimum traversal of a binary tree seems to be close to but shorter than that a star graph.
Graph Type |
Worst Starting Vertex |
Worst Case Minimum Traversal |
Distance Between Rooms |
Any Hamiltonian graph |
Any |
$n-1$ steps |
36.53 miles |
Path (linear) graph |
Center |
$(n-1)+\lfloor \frac{n-1}{2} \rfloor$ steps |
24.3 miles |
Star graph |
Center |
$2(n-2)+1$ steps |
18.2 miles |