Not sure about the package you're referring to, but after a quick search I found Quantum Methods with Mathematica (result 5) which gives the source code for their version of the QuickReIm package as
protected = Unprotect[Re, Im, Conjugate]
Conjugate[expr_] := expr /. Complex[x_, y_] :> x - I y
Re[expr_] := ...
NDSolve uses NDSolve`NDSolveMessage to do something like what @Sascha suggests in his answer. It creates (or loads) the messages on the fly, and defines them for the *NDSolve* functions that use them. Writing such a function should not be hard, but I will show another approach prompted by @belisarius's hint.
The main difference from NDSolveMessage is ...