a client will decrease their user licenses. if they don't remove user accesses on the day that the new license is valid, what will happen? can they be locked out?

Can't say I've experienced this particular scenario, but I know for sure they won't be able to add or modify any users' roles, since you are over the license cap. So even if they were able to keep those seats, the minute they have any turnover or user role changes it's going to be an issue. Also, as part of your license agreement, NetSuite says they can bill you for additional services you are using (e.g. storage) but the wording is much more broad, so in theory, if they somehow managed to hang on to those users, NetSuite could just say "well you're using more than is in your agreement and we're going to bill you for them".