Now that I go to my repo, I see some files that exist on the repo but not locally.
The files are stored in your git repository but they are not part of your recent code (workdir).
If you want to totally remove them from git (from history) you will have to clean the repository and delete them.
To do it you can use filter-branch
or to use this tool.

How can I tell my git repository to delete any files that don't exist locally?
Once git track files which you wish to remove you will have to first remove them from the cache (index).
git rm --cached
Which files to remove? you will need to have a list of the files you wish to remove. This can be done either manually if you know your files or generate them with script.
How to get list of files to be removed?
There are few ways. (format-patch
, log
and more)
Here is a sample on how to view the files which were committed (git > 2.5)
git log --cc --stat
