quota are usually real time.
However, there is not such thing as mail quota. There is file quota. This means your mails aka files in user hole Maildir folder but also ALL files created by the user ANYWHERE on the server. Particularly in the home folder, any ibays or any shared folder.
Mail are usually a small fraction of the whole files owned by the user. If your removed 5000 mails for a user, there are chances you only removed few ko and this will make little to no difference. But remiving dozen of video files of 600Mo-3Go each will make a difference. And yes do not forget to empty the recycle bin of samba if activated !