There is a thread running in ATC Issues
here discussing ways of contacting an aircraft other than 121.5.
CPDLC would be a great method if the message was available, aircraft would log on, crews were trained, however as in nearly all cases none of these happen let alone all three for it to work, it looks like CPDLC is just another system that most controllers will remember with a chuckle.
AirBubba - if you log onto Budapest 15 minutes prior to entry, how does the previous centre contact you using CPDLC? I ask as most of the sectors I control will be crossed by a B777 in less than 10 minutes. If they are already logged on to the next FIR before even entering the sector then doesn't that defeat the object in the first place?