This is a very interesting question. One of the most important considerations in patients on long-term immunosuppression is the risk of complications, whether infections or (more dangerously) cancer development; because of this if we can taper the dose then we would like to. This paper specifically discusses a lot of those risks. You mention prednisolone which is a glucocorticoid, and the side-effects (see also here) of chronic steroids (due to very wide-ranging immunosuppression) are well-known and always borne in mind when they have to be prescribed. The tapering of corticosteroids in long-term immunosuppression is often early to replace them with other drugs (mentioned here). With regards to the other immunosuppressives you mention, I'll mention mycophenolate mofetil and tacrolimus later with regards to how this is feasible biologically; with regards to cyclosporine, this study (admittedly old) has data illustrating the rates of rejection of renal transplants when patients withdrew from or tapered cyclosporine (here for financial reasons, but this drug also has significant adverse effects) and you can see from Figure 1 in the paper that although the patients who withdrew completely had many allograft rejections, those who tapered did not.
I'll start with answering your question about what clinical evidence we have for being able to do this; there have been quite a few studies which might help to throw some light on this. This study specifically considered kidney transplants, testing patients who were on standard immunosuppression for the 2 years after a transplant, and specifically measuring the quantity of CTLs (cytotoxic T-lymphocytes) reactive against donor cells, and they found that these cells were significantly downregulated in most patients 2 years after the transplant (while activity against third-party cells was mostly preserved). Since they found other T-cell responses to be unimpaired, they concluded that there was specific downregulation of the donor-specific cells occurring.
This paper also has some data which you can have a look at. This study specifically looked at moving patients from cyclosporine to azathioprine and mycophenolate mofetil and then tapering those. I've reproduced one of their graphs below which shows the activity of donor-specific CTLs before transplantation (the no dose group), 1 year after (still on high dose immunosuppression) and 2 years after (on low dose immunosuppression). The units are the ratio of activity of donor T-cells to activity against third-party T-blasts from spleen tissue (i.e. a control). Although you can see that some patients have ended up with increased activity after tapering, most patients appear to have low activities similar to (or even lower than) their pre-immunosuppression values, and these would be the patients considered for this tapering. This means that they now respond less vigorously to allograft cells than to control cells, and the ratio has decreased during treatment (presumably the reason why almost all of them have ratios under 1.0 before treatment is that the donor is not a random individual but matched for a lower immunological response):
And for another comparison with the body's response to non-donor substrates, the same study looked at response to tetanus toxoid. As you can see in the graph below, although the high dose caused the response to drop, it appears to have bounced back up again in most following the taper, similarly to the 3rd-party T-cell response but unlike the allograft response (the y-axis is proliferation of patient spleen cells in response to the toxoid divided by control rate):
As to the immunological reasons that we can taper the immunosuppressant dose, this is not particularly clear but there are known processes which might help to elucidate it. This paper (also on kidney transplants) suggests that there is a specific downregulation of the activity of CTLs directed against antigens presented by the direct pathway, and that this could be caused by anergy, deletion or regulation. The authors suggest that the most likely cause is an effect of the chemotherapeutics (here MMF and azathioprine) on the T-reg cells, and they speculate from the tests they did (the Discussion of the paper has the details) that the cessation of suppression of T-regs that occurs during the taper is what is responsible. They also mention a role for IL-2 signalling (necessary for T-reg function, and some immunosuppressants suppress it leading to rebound on tapering) and dendritic cells (whose costimulatory function may be altered by MMF).
As to the precise mechanism, it is not yet particularly clear, but it is thought that in the interaction between a suppressing T-reg cell and a CD4 effector T-cell, the latter actually induces the T-reg cell through as yet unknown mechanisms, so that continued activity of T-cells (e.g. in chronic inflammation or the presence of an allograft) may upregulate T-regs that suppress them. It is known that T-regs are important in downregulating chronic inflammation (presumably this is responsible for the pattern in the first graph I reproduced above where the activity against donor cells seems to drop more than that against control cells, even on high immunosuppression), through mechanisms which have been hypothesized to include CD4 T-cells undergoing receptor-ligand interactions with T-regs and providing signals to them to upregulate their production of IL-35 (which is important in suppressing all types of T-cells). Given that it is known that upregulated suppressive activity of T-regs in chronic inflammation downregulates the immune responses of all non-T-reg cells, it appears that donor-reactive T-helper cells will induce T-regs which will then downregulate donor-reactive CTLs. This paper I mentioned previously postulates that on release of immunosuppression this population of T-regs would bounce back and greatly downregulate the donor-reactive CTLs and T-helper cells.
This paper also mentions the fact that an introduction of tapered mycophenolate mofetil in liver transplant patients promotes immunological tolerance to allogeneic transplants. They mention the effect of this on T-regs as well as other immune cells.
For interest, this paper presents some interesting alternative speculation on the nature of the T-regs involved in organ transplantation tolerance. In certain cases, self-tolerance may develop to 'new' tissues, and the authors postulate that the main T-regs involved in transplantation tolerance are newly formed in response to the prolonged presence of the allograft, rather than predefined. Because of this, the tolerance might develop to some extent regardless of the chemotherapeutic regimen.
Finally with regards to tacrolimus, this study has data on the immune response during weaning off the drug after an intestinal transplant. They found that patients with a low immune response prior to weaning had a better response to the weaning, and that their immune function remained low after weaning. This is a bit different to the MMF situation I mentioned above where immune function in general seems to return and only donor-reactive immunogenicity remains low (this tacrolimus study doesn't specifically mention the effect on infection rates, but their Figure 7 seems to imply that those patients with low immune function (presumably those weaned) had lower intervention rates). Specifically the authors conclude here also that self-downregulation of the immune system (probably by T-regs) is likely to be the cause.
So in summary it is not yet fully elucidated as to why we can do this, but the upregulation of T-regs that downregulate donor-specific effector cells, and (at least for certain chemotherapeutics) the release of T-reg suppression on tapering may be important.