If it starts with random letters/numbers where the username would usually be before the @ then it is your domain that has been harvested and that can happen without the link.
I get this kind of mail for domains that don't have web pages associated with them so there are no links to be harvested.
Your web host may offer a "black hole" facility which means that any mail that is not addressed to a bona fide account will get dropped into a black hole and not delivered. But that does mean that you have to be sure to set up a mailbox or redirect for every variation to which a genuine e-mail might be addressed (e.g. [email protected], [email protected], [email protected]).