Surely a) is an easy enough solution.  Code to register/unregister
a callback says something like
  Register(Callback_Access);
instead of
  Register(Callback'access);
Do you ever have a case of multiple tasks registering the same callback
routine?  If so, how does one unregister its callback as opposed to
its sibling's callback?
  How about the "laundry ticket" method
  My_Registration := Register(Callback'access);
followed later by
  Unregister(My_Registration);
You could even have the laundry ticket My_Registration be a controlled
type so it could be guaranteed to Unregister itself when it goes away.
  If you have piles of existing code containing
     Register(Callback'access);
you could make the Register procedure look at the code at location
Callback'access and, if it's a short wrapper, simulate it to find the
real routine.  You would need some information on just what sort of
code your compiler generates, of course.
  I don't think I understand exactly what you want to do.  There seem
to be several solutions with minimal impact on existing code.  It
seems unlikely the Ada rules will change any time soon, especially
since they appear to have a very reasonable and understandable justification.