Perforce VCS behavior

Hi,

If we are using perforce in our vcs root and we don't have "Clean all files before build" checked it seems whenever a file has been deleted from perforce that the file isn't removed from the checkout directory when it takes that change.  Is this a bug?  Is this problem solved if you do an "agent side" checkout instead of a server side?  Please let me know as this has bitten us more than once.

Thanks,
Jason