If your client uses caching that could as well be the problem yes.
The plugin tries it best to stop caching software from caching the denied message however if the caching software is configured to ignore or overwrite the caching headers the plugin sends a legitimate user may receive the cached result from a previous user that received the denied message.
I would recommend against using the plugin for blocking users from the frontend in combination with caching unless you fully understand the caching software. Using the plugin in combination with blocking the backend should not be a problem as caching should not be used for the backend.
If you use the IP check from within the plugin it should also indicate if the user is blocked from either frontend or backend as well. For instance:
IP Adress 70.28.11.95 belongs to Canada.
This country is not permitted to visit the backend of this website.