Apparently players aren't getting "the ip address you have joined from is linked to a banned player"
message when they're trying to rejoin. Could this have to do with running it behind a bungeecord proxy?

Hm with IP forward this should either always work or always not(if buggy). That's odd...

Is ip forwarding enabled correctly? Check player ip addresses via /bminfo. If it is, this could be a bug.

Ip forwarding is enabled correctly.

Though we also have an issue where only half the players get the actual shutdown message on spigot server reboot (not due to BM but happens). Could this be related, because of bungeecord?

Sorry for the delay. @Theepwner are you running in offline mode (both BM and bungeecord)? If so, there was a bug with the handling around kicking/retrieving bukkit players. Should be fixed in the latest snapshot, see #678

No, but I haven't had this issue since.