I would sell such a laptop only without a hard drive, regardless of all the methods that exist to completely erase the data, the risk is always there. In addition, if the laptop has a classic hard drive the performance of such a device can be significantly improved by installing a solid state drive (SSD) which is not a big investment (around $50 for 256 GB drive).
Or should I just surrender to my paranoia, buy a new drive, and take out the current one?
If you want to be completely safe, then either install a new one (preferably an SSD), or try to sell a laptop without a hard drive.