I still do.

My first clipless has laces, and I liked them. There may or may not have been velcro then.