Yeah, that's what I suggested first (and indeed Dan has now opened a bug for to implement it in NM), however it is possible to break it down further like I was trying to describe later:
1) scan the last channel
2) scan the known channels for the last SSID
3) scan all (remaining) channels
The intermediate step only makes sense if those known channels are a relatively small subset of all channels, but with typical installations they will be. In fact, for many networks like your home network 1) and 2) will be exactly the same because you only have a single AP, but for typical enterprise networks 2) will still be better than 3).