Christian,
There are certainly many barriers that need to be faced and then addressed, but I hope you are also seeing the incredible benefit of developing and maintaining a relationship with your graduates. Our alumni are of GREAT value to our institutions. It sounds like your job will be to sell that to others at your institution.
Use your contacts with alumni to gather their success stories and then begin to creatively share those stories. Our graduates are walking breathing advertisements and investing a little in them is 'way' cheaper than the money we give our marketing departments.
June Gudeman