It depends on the bandwidth you require. Sample rate determines the maximum single shot bandwidth, and memory depth determines at which timebase settings you can use the extra sampling rate. I think the Rigol DS1052E is limited to 500MS/s with long memory in single channel mode, and 250MS/s in dual channel mode. I believe the Instek GDS-1062A can do 1GS/s with long memory enabled.
So basically, the memory amount dictates the sample rate, i.e. maximum sample rate = record length/(time/div*10) with saturation to maximum banner sample rate. Maximum sample rate matters only when you are measuring high-bandwidth single events in short timebase settings.
Actually it's also the other way around: long memory is useless on a fast timebase without a high sample rate to fill it all. You need both for single shot acquisitions of signals with high-frequency components. You can work around short memory length on repetitive signals by triggering on the right part of the signal, and work around sample rate by equivalent time sampling (if it's well implemented).
I agree that it depends on your application. I recently was observing a ~1ns rising edge in a circuit: don't really need more than a screen full of data, but do need fast sampling rate to sample the fast edge. I've used a TDS-220 for a number of years, and I rarely had problems with the 2.5kpoints/channel memory. An analog scope doesn't have more than one screen of data either

. But for some applications, especially if it's hard to trigger on the phenomena (or if the scope has crappy triggering), long record length is great.