Leopard Network Shares and browsing are unreliable

I have two macs, running Leopard 10.5.8. One is the 13" MBP connected via WiFi, and the other is a 24" 2008 iMac, connected via ethernet.

There are at least another 6-10 machines (windows and mac) awake on the network (with shares) at any given time, yet there are plenty of times where I cannot see any devices/shares in either my "Shared" section in Finder, nor can I see any computers in "Network" in Finder.

Restarting doesn't help. I've restarted all the networking gear in the house to no avail.

Our network is a series of gigabit switches connected to a D-Link gaming router. I believe we use OpenDNS, and our provider is Cox.

I hate having to use "Go -> Connect to Server" to browse to commonly used file shares (by IP). I'd like to know why my shares do not always and consistently appear in Leopard.

Edit: I ran OnyX this morning, and performed the cleaning and maintenance operations (including disk permissions) on both my Macs, and at least one of my macs has started showing network devices again. (the other is still going). No idea how long this will last.

Any ideas as to what is causing this issue, and how to prevent it?

Edit 2: Aaaand there the shares go again. So running OnyX is not a permanent or reliable fix for this issue.

Edit 3: After a clean reinstall and update, network shares are still unreliable. The SMBClient command mentioned in comments shows me the information it's supposed to show, but the shares do not appear in the shared section. They'll also vanish at random and reappear at random throughout the day.

Solution 1:

This is not an actual fix to your problem, but it should eliminate the headaches that you are experiencing.

A. Create a folder called "Network Shares" or somewhere in your user directory or possibly in a shared directory. Drag this directory to the finder sidebar under Places.

B. Do the following for each share that you want to connect to routinely:

1. Use Command-K from finder to mount the shared volume. This should add the server under shared in the finder sidebar
2. Go to System Preferences -> Acoounts (Under System), select your account and open the login items tab.
3. Click the plus button under login items and navigate to the share that you want to connect to.
4. This gets a little tricky here. For some reason, you cannot create an alias in finder (Command-Option Click and drag) to network shares, you can do this to any directory under the network share, but not the share itself, so if you want the share itself accessible as an alias, you have to use the terminal to create a symlink which is essentially the same thing. If you need to do the symlink thing here are the steps.
5. Make sure that the share is mounted.
6. Open terminal.
7. Navigate tothe folder you created, Network Shares (if you created this folder directly under your home folder the command is cd ~/"Network Shares"/.
8. create the symlink :ln -s /Volumes/"Share Name" "Name of alias file" (the quotes aren't necessary if there are no spaces in the file name.

What you end up with is a folder full of aliases that point to all the shares you access frequently.