It depends on the structure of the network and the details of your configuration.
When you have a default route that goes to internet via NAT and you have tried to reach the remote system before you added the route, yes it could happen.
This is because the router has setup a NAT translation entry for your connection, and will re-use that after you have added the route.
It should not really be required to reboot. Waiting a couple of minutes should do it too (as the NAT entry that has not entered established state will soon time out).
To prevent this kind of problem, add the following routes to each router that you configure:
/ip route
add distance=1 dst-address=10.0.0.0/8 type=unreachable
add distance=1 dst-address=169.254.0.0/16 type=unreachable
add distance=1 dst-address=172.16.0.0/12 type=unreachable
add distance=1 dst-address=192.168.0.0/16 type=unreachable
I always do this as a standard step to newly configuring each router (not only MikroTik!)
With this in place, you should not have that problem and you prevent other problems as well.