There is a registration_errors filter, which native errors go through and which allows you to provide your own. Returning filled in WP_Error object in this filter will smoothly prevent user from being created.
The one downside is that that filter is not passed much additional data — only login and email. You will probably have to fish your custom data out of global $_POST state for the check.