Custom tables can simplify your code, improve performance and help avoiding conflicts with WordPress’ schema changes in the future. Don’t hesitate to use one if you need it.
The extra complexity comes from two other factors: maintenance and multisite.
Maintenance: manual or automatic backups might omit custom tables, so there is a tiny risk that the data in custom tables can get lost. That’s up to the administrator of these sites, it cannot hurt to point that out in your readme.txt and plugin page.
Multisite: If you add a custom table in the main site of a network, there is no way to detect per code whether this table is meant to be a network table (like the users tables) or a site table (like the posts table). WordPress’ naming scheme just doesn’t offer a distinction. This is a problem when you want to duplicate a site in a network per code. So again, your data might get lost during that process.
There isn’t much you can do about that. Some cloning plugins offer hooks to include custom tables. You have to add support for those hooks in your code. So in this case, the extra complexity is on your side.