In order to avoid having to keep track of all handles, there is a simple alternative.
You can use the 'HandelVisibility' argument when calling plot, in order to automatically hide the extra lines/markers from the legend. This way you can have a common replacement called plot_fewer_markers (I have actually implemented this and I'm going to upload it to file exchange when I find time, together with some other useful things), which then plots 3 times: once with a visible handle, only the first point, using the complete style you specified (e.g. 'r--o'), once more only the line with all points (or subsampled, but that's another story) with the style 'r--' and invisible handle, and one last time the markers, using fewer points with style 'ro' and again invisible handle.
In this way you can still continue working as usual and just call this function, the result will be as desired.