Magic was the software in use at a small company of fewer than 100 employees. Although that environment was supposed to be Magic's sweet spot, end users would do just about anything to avoid it. It was klunky and only barely fit the need.
I have used Remedy off and on for over 10 years. It is easy to use, has an understandable user interface and we had good levels of compliance from our 2000 users. From a web client, an end user was led through a series of questions that generally provided the service tech with enough information to fix the users problem quickly and get them working again. Rarely did the tech have to call the user but often did as a courtesy to schedule an appointment desk side.
Remedy was also robust enough to allow us to manage collaborative scheduling such as Change Management.
I am not familiar with Unicenter or Service Desk Express.