Cheap filler note paper is a source of difficulty when writing(ball pens will skip, dark inks will bleed, scratchy pencils and nibs will tear). The index cards work, but I would also go for the slightly more expensive paper brands one can find on JetPens. If you're going for a stationary experience, investing a little more in it goes a long way.
I like use a 5.5 x 8.5 or 9 x 12 Strathmore 300 Sketch tablet for notes. They are sturdy and the paper is quite good. They are a pain if you want to scan/copy them as the paper is either smaller or larger than standard letter size.
Yes I also use sketch pads with no lines (The grey spiral-bound ones sold by WHSmith in the UK). I don't understand the attraction of lines given that software is hard to describe without diagrams.
And longevity. I have my note books from 20 years ago on the same shelf as my notebooks from last year. Apart from pictures (I had a digital camera in the mid nineties) The number of files that have survived the transition between a dozen computers is not that high.