How long is it reasonable to wait for a graduate student or postdoc to obtain a visa?
Visa issues can be seriously problematic, especially given the high degree of arbitrariness that is often applied toward people coming from disfavored countries in the developing world.  For example, consider the apparently arbitrary visa denials faced by students coming to the US from Iran. 

Given this I would recommend using the following criteria in making a decision:


Is the person being reasonably aggressive in acting to secure a visa?  If the student is attempting to secure a visa and being blocked/slowed by outside forces, time to secure the visa should not be held against them.  If the person is not bothering to act towards securing a visa, then it's the same as not bothering to physically move, and they can be let go with a clean conscience.
Is there a concrete time limit on the funds? If external requirements mean the money is on a short-term "use it or lose it" status, e.g., a 1-year externally funded project that includes a task for a postdoc, then the person may be disqualified through no fault of their own by the circumstances.  In this case, I think it is appropriate to put the deadline early enough to have a reasonable chance at hiring an alternate person to fill the post.  The deadline should be made clear to candidates as early as possible, however.


If the timeline can be flexed and the person is being reasonably aggressive in pursuing the visa, however, I think that it is morally important for the ideals of science to continue to extend the offer.  Science should be, to the extent possible, practiced openly for the general benefit of humanity, and it needs all of the diversity of strong intellectual contributors that it can obtain, no matter where they may originate, so long as they are honest and open contributors.  Giving a person time for visa issues to resolve is one small but important thing that an individual scientist can do to support that ideal.