Is that even possible? Shouldn't the recipient email id need to be created first to be addressable?

Of course, the technical term for that setup is 'catch all', you can set this up with your email provider. You can send your email to "ghywertelling@gregegan.net", for example.