Transcoding is a tricky problem that can be tackled in many ways.
1.0 proposal
A perfect transcoding system is impossible to get running in the first try, but a limited 1.0 version would be a reasonable first approach. There are different ways to do it, one must be chosen instead of trying to do everything at the same time.
bottom up
Most transcoding tools use mencoder, not because it has the easiest UI, but because it just works.
A reasonable 1.0 target would contain a gst-encoder tool similar to mencoder that allows most of the popular transcoding usage. It should be easy to specify the audio and video codecs, as well as the container format, the user shouldn't care about what is the input, just the output. Resizing, cropping and resampling should be easy to specify too.
top down
Another approach could be to target certain mainstream formats: like psp, maemo tablets, ipod, etc. And create a tool that converts the clips automatically finding the parameters based on the profile.
Current solutions
There are several approaches that have been tried:
GEntrans
gst-identify
gst-identify is a tool that allows smart scripts to query for the capabilities of a clip. The output is easy to parse precisely for that purpose.
maemo transcode
maemo-transcode is a smart script that find out the perfect settings to transcode a video to the different Maemo devices. It's extensible so it can be used for other devices too.