Have you removed users from any other groups like the contributor group  etc that they may be members of?
Check the permissions on the new group just to make sure it hasnt added additional rights.
Let me Know

I created  the minimal rights  site group,
then created a new user, and added him to the group. I went back and
checked to make sure he wasn't added to any other groups. I'm certain
it isn't a cross-group issue, but we're still seeing all the Actions I
spoke of before.

I cannot figure out why this is happening. I'm beginning to believe
that something went wrong during customization of our portal. We didn't
use FrontPage so I'm pretty certain it isn't unGhosted, but the problem
may lie elsewhere.

You could try re-inheriting the permissions from the top level then starting again.

One thing that might be your problem  is that you are an Administrators
group member (Windows security) on the server running SharePoint. If you
are, then any security that you set in SharePoint will be ignored, and
you will have full rights  to do whatever you want to do.

Make sure that you are not authenticating as someone who is in the
Administrators group.

Clear your cache. And try to get at it from a remote machine. Also, ensure you’re not logged on as the local admin the box.

Any chance that this user  is in the SharePoint Administration group  (a
single AD group identified in Central Administration providing global
administrative rights). Could they be the owner/secondary owner of the
Virtual Server or Site Collection or potentially identified as a Site
Collection Administrator.

All of these folks (and maybe others) have cart blanch access  to do and
see everything whether they are explicitly listed or not.