I think the problem is not with the profile  but with the index which
has been created when you had assigned it some category. I think you
need to remove  the index for that document.
A workaround could be to purge all indexes and perform a "full build"
for the indexes.
Try this and then try searching for that document.

Post your results. i am also keen to know

How do I re-index the site? I looked into that yesterday. I went into the
SPS admin program and reviewed the services but could not figure it out.

Go to the SPS Admin-Tool and rightclick on the Workspace where it says
"index reset" or so and after having resetted the index start a full index.
I have done it two times or so and then the changes could be seen.

Be aware that this will take time depending on the size of your workspace.
Do not try to do things that are gnawing on the servers resources etc. Just
as a precaution.