NM scans periodically, and will trigger a scan when you do stuff in the applet.  There are ways to tune the scan algorithm to be more responsive, but NM won't ever include a "scan now" button.  Some of those reasons are explained here:

http://clarkbw.net/blog/2007/10/16/refresh-in-reactive-displays/

I believe that tweaks can make the scan behavior better.

Okay, what happens if you leave your laptop on and move between two locations with a very different set of wireless networks?  It takes Network-Manager probably 15 minutes to recognize the change in availability of networks.  Also, if you have a radio off switch, it takes a similar amount of time for NM to recognize that it's been turned off or on, providing for a very frustrating user experience.

These are deficiencies in the scan algorithm and certainly dont' require a "refresh" button.

First, NM only holds on to wireless networks for a maximum of 6 minutes.  If the network hasn't been seen in 6 minutes, NM gets rid of it.  Second, you must not be using a recent version of NetworkManager, because 0.6.5 SVN and 0.7 both have rfkill support for dell laptops and laptops with Intel cards, and that does work correctly.

Can you tell me exactly what version of NetworkManager you have (ie, the package version from your distro) and what kernel version you have?

I am using nm 6.5, kernel version 2.6.22, and have a broadcom wireless chipset.

I guess my initial estimate of 15 minutes was wrong, if I disable the radio, it takes NM 6 minutes to realize it.  If I run iwlist scan, the results are immediate (of course, I shouldn't have to do this, because the whole point of having a fancy GUI like NM is to provide a convenient and fast alternative than using the command line).

Look at this from the standpoint of the beginning linux user who doesn't know how to connect to wireless networks via the command line.  All they have is an unresponsive NM applet, making their initial linux experience frustrating and unpleasant.  They won't know to use the command line to connect to their desired network, and even if they did, they wouldn't know what to do.  

Bottom line: If there are deficiencies in the scan algorithm, they either need to be fixed immediately, OR a workaround (ie. refresh button) needs to implemented until they are fixed and work on all cards.

*** Bug 465780 has been marked as a duplicate of this bug. ***

If you enable/disable the radio, does NetworkManager notice the change and disconnect you within 10 seconds?  0.6.5 and later have support for rfkill switches, but only for Dell laptops (if you have the dcdbas module loaded, which you should) and for Intel PRO/Wireless devices, because those are the only devices that HAL has rfkill support for.  There is a generic kernel rfkill framework in 2.6.23 and later which will broaden this support as drivers get moved over.  I don't believe that bcm43 has the rfkill support in 2.6.22.  You will have to wait until HAL supports your laptop's rfkill switch, and when that happens, NetworkManager will Just Work with it.

*** Bug 510726 has been marked as a duplicate of this bug. ***

r3262 of the stable branch fixes some deficiencies of the scan algorithm.  NM
will scan every 20 seconds for 2 minutes, then bump the scan interval up every
120 seconds thereafter.  If the device is deactivated, NM will bump the scan
interval back to 20 seconds for 2 minutes, then up to 120 seconds thereafter. 
If the user interacts with the NM applet, NM will bump the scan interval back
to 20 seconds, and immediately scan if no scan was done in the past 20 seconds.
 This should fix many of the complaints about the speed of updating.

The other issue might be the driver; some drivers (especially mac80211 based
ones in recent kernels like ipw4965) are still buggy and don't report complete
scan results when asked to scan.  You can test this by executing (as root)
"/sbin/iwlist <wlan interface> scan" and seeing how many APs you get back, and
comparing that against how many you expect to get back.  If the driver is
broken, then NM certainly isn't going to work very well.

*** Bug 471841 has been marked as a duplicate of this bug. ***

*** Bug 564296 has been marked as a duplicate of this bug. ***

The changes in Dan Williams' comment #8 sound like the perfect solution, what version of NetworkManager would be the one that would contain those fixes to the algorithm?

The 20 second / 2 minutes aren't adequate.  Try waiting 20 seconds right now before you read the next paragraph.  Try waiting 2 minutes.

I have an auto-join AP I plug in at work (my laptop is not suspended between my residence AP and work, 5 minutes away) and it never seems to be recognized.  I don't wait 2 minutes.  It isn't the driver.  I can do "sudo iwlist scan" and it appears instantly in that output.  It is in the card/driver's list, but NM won't bother rechecking the card for new APs for who knows how long.

It will pick up every stupid coffee shop and hotel I've driven anywhere near on my way to work (another bug report was the NM list growing too large with pages of entries which won't expire for 6 minutes) - maybe the applet is for war driving instead of actually allowing a user connection since the AP I want to connect to (and will automatically connect) won't be found for what seems like forever while I will have 6 minutes worth of cached beacons from my drive in.

You do have a "refresh" mechanism - disable and reenable wireless.  That works.  100%.  Instantly.  Instead of making the applet user friendly, I have to DO THIS STUPID HACK EVERY DAY TO JOIN THE NETWORK.  At least unless I go get a coffee and bagel or something else which takes several minutes.  If any web page took a minute on average to load, you would complain.

Tweaking intervals is not a fix nor does it even address the problem.  I'm at this particular AP for over 9 hours and DON'T CARE IF THERE ARE ANY OTHER APs although it will scan for them hundreds of times FOR NO REASON.  Almost every card I have will FIND AN AP BY ITS BEACON AND ADD IT TO ITS INTERNAL LIST WITHOUT SCANNING.  That is what the beacons are for.  You would only need it for some strangely configured AP or badly supported network hardware.

Don't complain about bad wireless drivers when you aren't effectively supporting the working ones which have the complete AP list available one or two system calls away without any scan - the list is always "current" but you won't use it.  My AP is already in the list inside the card.  You won't show those beacons for 2 minutes because you won't look at what the card might have until your own refresh interval.  Then it seems you will ignore the fact it found any APs by their beacons and just initiate a new scan whether I'm connected or not - am I correct about this?

I'm not sure what you are trying to achieve - some abstract UI artform maybe - but actually allowing me and other users to quickly and easily connect to an AP which is on, active, and next to my computer isn't one of them - for the reasons given.  Refresh buttons are evil so the Gnome team thinks it should force the user to wait a minute or two instead.

You could initiate a scan (or just read the collected beacons) when I popup the menu as it might be a clue that I want to connect and I may only do that two or three times every day instead of every 2 minutes over the hours I'm not switching connections.

You have automatic intervals which are wasteful (active scan v.s. hearing beacons) especially when connected or idle, and horribly, annoyingly slow when a user wants a connection.

Both Windows and Mac update the list upon hearing a beacon (perhaps with a too fast to notice refresh mechanism since with the menu open my AP appears a few seconds after powerup).  Windows has a refresh (which does a scan - for APs with beacons off but visible).  Gnome has a static list which will only be updated by a background task doing a full scan an average of a minute later.

Note the "If the user interacts with the NM applet, NM will bump the scan interval back to 20 seconds, and immediately scan if no scan was done in the past 20 seconds.".

That behavior means that simply opening the network manager applet would essentially be a "rescan now" button, no extra step of actually clicking any extra button would be required.  Which is an elegant solution to the problem.

So the major question that remains is what version number of network-manager will or does actually have that change.  7.0.1?  7.1?  7.2?  So that users can tell if they have the version necessary to make that change happen installed, and whether it is working as stated for them.
For example, I from ubuntu intrepid, which had the broken network-manager behavior, to ubuntu jaunty, which no longer had broken network-manager behavior.  But I can't be sure that that wasn't a fix of the "return-from-suspend" check of ubuntu, or whether the network-manager version 7.0.1 includes the elegant behavior attributed to the svn version r3262.

Thomas, for my part, all I can recommend is to try to get either version 7.0.1 or the very latest: 
http://ftp.gnome.org/pub/GNOME/sources/NetworkManager/0.7/ 
7.1 installed, even if your distro hasn't updated to those versions yet, as the fix may already be available in one or the other of those versions.

I'm using Jaunty and should have several "push" archives enabled, but I will just recompile the version myself (I have a small list of things I have to manually add anyway and I will add it).

I'll downstream an update bug report or request so it gets into a patch or the next next release (and/or the previews).

I apologize for the rant, but the update didn't make it to this bug report and all I read was the "We are never ever going to fix it - see this blog entry" post and nothing further.

THanks for all the hard work.