Should you use a 404? I could see arguments both ways. A "no results" result, is still a result. So it's not a 404.

I would do a 404 if you try to link to a product that does not exist, but not for a zero results found page.

BTW madars don't use url shorteners here - even for really long ones.

<meta name="robots" content="noindex,nofollow"/>

in the header. That's the proper way to not allow a page to be indexed.