AD Software Deploy to User requires Local Admin rights !??

Hi

When you deploy software (assigned or published) to a USER, is it
normal that the user requires Local Administrator rights for the
installation to work? That seems crazy!! That would mean that the user
would need to be a domain administrator, to ensure that they have local
admin rights to whichever computer they happen to be using (so that the
software follows them around as intended).

The software I am trying to deploy is MS Windows Messenger 5.0. The
application does appear in Add New Programs, however when you attempt
to add it, it errors: "Windows Messenger 5.0 was not installed. This
installation was interrupted. No changes were made to your computer
system."
Note: Everything works perfectly if the user is a local administrator.
Note: Server 2003, Windows XP SP1.

I heard about the "Always install with elevated privileges" policy, so
I applied that to both the user and computer in AD, ran a gpupdate
/force, and I get the same error as above.

Am I doing something wrong, or is this how MS have designed it?

Thanks,
Nick