I'm almost always at "another location". The servers I manage are all many miles from me. That's what SSH is for, secure remote administrative access to Linux servers... and more. Anyway, sounds like it's not a "missing" file(s) that is your problem, it's permissions. Take for example:
# ls -l /var/lib/mysql/mysql/host.MYI
-rw-rw---- 1 root root 1024 Mar 27 2005 /var/lib/mysql/mysql/host.MYI
If you looked at the file and saw something like that it would mean the file is owned by the root user and the root group. it's (rw-) readable and writable by both the root user and anyone in the root group but (---) not by anyone else on the system. The "mysql" user is in the mysql group. It would have NO access to the file in that scenario. By default the mysql server process fires up as the mysql user, inheriting all the permissions that user has. If you override that to start up the mysql server as the root user, it would have *all* privileges on the system and could read/write any file.
/var/lib/mysql contains "mysql" and "test" but they aren't files, they're subdirectories. Inside the mysql subdirectory are host.frm host.MYD host.MYI and similar files. Each grouping of those represent a MyISAM table in the mysql server. Run the client and "use mysql;" followed by "show tables;" and you'll see 1 table per set of .frm/.MYD/.MYI files in /var/lib/mysql/mysql/ directory.
"grep" is the tool you're remembering, it's in the "top 10" of every Linux admin's "toolbox".
# rpm -e <packagename> will remove all binary files, libraries, etc.. What it will commonly NOT remove is configuration and data files. In other words I can install mysql, tweak /etc/my.cnf to my liking, create some databases and import some data in them and then de-install mysql in this manner. Later I can re-install it either with rpm or yum and all my data is still there. (of course I'd back it all up just in case). Anyway, that's why I recommended if you do the de-install/re-install to manually delete the /var/lib/mysql directory as it's likely the rpm -e will not get rid of it. I doubt you need to do that though, a simple "chown -R mysql:mysql /var/lib/mysql" will probably fix you right up.
PS. I'm in the habit of almost always using grep as "grep -i" since that makes it case independent. It would get a "hit" on "mysql" as well as "MySQL" that way.