One solution that works in a fair number of cases is to put the code that needs increased privilege and put that into a setuid helper program. Then, the entire application can be installed without setuid bits, and you only have to ensure that those few hundred lines of your helper application are secure.
Of course, you have to make sure that you don't open up new holes by making your helper program too generic. As a silly example, consider the utmp issue. When xterm starts the user session in a pseudo terminal, it wants to add an entry to the utmp file that contains the name of user and pty. When it exits, it wants to remove this entry. So what you want is a helper program that does exactly this. If you design your helper program, you must make sure that it doesn't allow users to edit arbitrary utmp entries.
In the utmp case, this is not too complicated. There's already an implementation by someone at RedHat called utempter. The program obtains the user's name by starting the real uid, and retrieving the passwd entry for it. Obtaining the name of the tty is a bit more complicated, but basically xterm has to pass the tty's file descriptor to utempter, which makes sure it's a tty device owned by the calling user.
Another example is verifying passwords. On a system using shadow passwords, any application wanting to verify passwords must be privileged.11.3 In KDE 1, all screen savers were setuid root because of this. Of course, that's a very bad idea because the KDE libraries are huge and were never designed to work safely in a setuid application. The solution for this case is another helper application for checking passwords. Again, we must make sure not to make this application too generic: if you create a helper that lets a user verify any other user's password, you defeat the goal of using shadow passwords in the first place, which is to avoid brute force guessing of passwords.11.4 So the password checker should be restricted to checking a given password against the account of the invoking user. There are two implementations of this; one is kcheckpass that comes with KDE. Another is pwdb_check which is part of the PAM library.11.5