How about just re-using, by writing on the back, the reams of paper that is printed on one side, that your printer spits out, and much of which is discarded. Reduce, Reuse, Recycle.
For portrait lined 3x5s, if you can't find them, you can just use a guillotine on a 5x8 card and get two 3x5s and a nice business card size-ish scrap. And business card stock for an index card todo is way overkill. Also 2.5 cents vs. 10 cents per tododeck card.
The very 1st photo after the header on that homepage sends the opposite message to your "Paper is making a comeback" with it's clearly computer-generated text on this image:
http://f.cl.ly/items/0v1m0x0a2a35420m3a3L/styles.jpg
Handwriting the text, even if it were slightly less legible, would be better than doing it in a stock font in Photoshop.