WSS stores user information in the UserInfo table in each content database.
MOSS uses both the UserInfo table and user profiles in the SSP. The attributes
of a user are copied to the Userinfo table when a user first accesses a
SharePoint site. After that if you are using WSS the only way to update
attributes like email is to edit the record directly, which can be done either
by the administrator or the user. If you are using MOSS, then the user profiles
can be setup to run a recurring import of information. This will update most
fields in the user profile including the email address. (Note: Some fields like
Display name don't update appropriately). Changes to the User Profiles are then
synced with the userinfo table by a timer job that should run every hour, but
I've seen it take a day or so before the change  comes through. Since, the email
address that users  see when they click on a user is the one stored in the
Userinfo table you need to wait for a substantial time before the change
replicates through the system. You also need to have Profile Imports running to
pull the change in from AD.

Can you explain what the data in the userinfo is used for? For example, if I was
to remove all of the user profiles, what effect would that have on my system?
It seems odd to me that I only have 239 user profiles but many more users  that
that.

The userinfo table is used primarily because WSS doesn't have Profiles. So
anytime you need user information in the base product it gets it from the
userinfo table. MOSS adds the availability of Profiles which can be extended
with additional attributes and populated using an import from other sources like
Active Directory. Instead of writing basic functionality to detect whether MOSS
is installed or not all the basic stuff uses the Userinfo table. MOSS specific
things like audiences use Profiles. Since UserInfo is only populated when the
user first visits a site MOSS also includes jobs to synchronize changes from the
Profiles to UserInfo.

Removing all profiles wouldn't have any effect on the UserInfo table, except
preventing it from being updated. Basic sharepoint  functionality would continue
to work. Profiles are built based on an import from AD. Depending on when and
how that import was run it could easily contain only a subset of users  in
SharePoint or AD. This is particularly true if you use different authentication
mechanisms or have a multiple domain  forest. The default Import settings only
import from one domain, not the entire forest and no non AD users are imported.
Both of these can be changed  by configuring and running the profile import
again.

I think I now understand the user profiles and how it interacts with the
UserInfo table.
What would happen in I deleted all the records from the UserInfo table?
I am trying to find a way to automatically have all the users  updates with a
refreshed e-mail  address from AD.

The point is that if the updates are being reflected in Profiles then they
should also eventually be reflected in the UserInfo table. If the changes
aren't showing in the profiles then you need to re-run or re-configure the
schedule for Profile Imports. I wouldn't delete the users  in the UserInfo
tables since these entries are tied to permissions and users may no longer be
able to access the system if you delete them from UserInfo.