Hi,
It could be a bug that has already been fixed, either because you don't have the latest version, or you don't have a hot patch we've added since the latest release, or one we didn't find yet. But it could also just be a setting issue and it is exacerbated by something else (for example, the user doesn't fill something he needs to, but the template doesn't display the error messages coming from HikaShop to warn the user and thus he doesn't know what's wrong).
Again, it's hard to say without even a link to the shop to check on the situation.
And also, what you say in your last message seems to confirm that it's not linked to the payment plugin.
Also, the address is only mandatory if you have the "address" view in your checkout. If you've deleted that view form the checkout, then the address is not mandatory. If the user fills it during the registration, then it will be attached to the order automatically, but otherwise (if for example he logs with a user account without an address previously added) he can place an order without an address.
Similarly, if you're using PayPal Express Checkout, based on how your checkout workflow is configured, it might be possible for the customer to bypass the checkout (that's the goal of this plugin) and then if PayPal doesn't provide any address information for some reason, the order could be created without an address.
Again, without looking directly at your checkout, I can't say for sure what the problem is. I would need to to provide a link to it to check the situation.