The query planner isn't very clever at times. "At times" actually makes it worse, because performance bugs surface sometimes.
Anyways, the result is multiple orders of magnitude difference. What takes 0.3-2ms suddenly takes hundreds of milliseconds or even seconds to complete. Multiply that with millions of execution count and there is a problem.
Sometimes SQL Server WILL NOT CHOOSE covering index (with many include columns), because it also evaluates index size. And if SQL thinks that some seek on clustering index is specific enough for parameter value A, then it is disaster with parameter B.
Good thing SQL server features plan guides, where you can tell server which index to use or provide other hints. Saves the world when dealing with 3rd party applications.
The stuff you have to do deal with your db grows as row count grows. If configured well, can support billions of rows, as we see from this post.