Custom Application Deployment

I seem to be having a hard time with this project at work and I know I'm not the only one who has dealt with this type of project before. The company I work for develops software and as a member of the data center team we have to take their releases/patches/updates and apply them to all the servers (including QA). The problem is there is no real way to make sure that patches are being applied correctly when doing this by hand (bc of the number of servers). We are also in a mixed Linux / Windows environment @ the moment. I'm in the process of migrating everything to linux but it will be a while still. I have tried some scripting, but have run into so many walls. I looked at things like cfengine, puppet, etc and there is no real windows/linux solution.

Anyone have any suggestions??