The overall response of elasto-viscoplastic polycrystals demonstrates non-Maxwellian, long-memory effects, while constituent single crystals show Maxwellian, short-memory behaviour. To characterize this emergent behaviour, this work presents analytical homogenization estimates for the elasto-viscoplastic polycrystals and demonstrate that large viscoplastic nonlinearity or anisotropy for the single crystals lead to strong long-term memory effects on the overall response, and thus cannot be captured with a Maxwellian model for the overall response. Comparisons with the Maxwellian approximation for the overall response, obtained by separately homogenizing the elastic and viscoplastic components, serve to characterize the long memory effect. It is found that the strong long memory effects for polycrystals consisting of nonlinear or anisotropic grains are caused by rapid changes in the inter- and intra-granular field fluctuations. Under creep loading, ice-like hexagonal close-packed (HCP) polycrystals deform with significantly larger strains than those estimated by the Maxwellian approximation, while for linear face-centered cubic (FCC) polycrystals, the long memory effect is rather minimal. For constant overall strain-rate loading, significant improvements over the Maxwellian approximation are also observed for the HCP polycrystals, especially in the transient regime. To assess their accuracy, the new estimates are compared with available full-field and experimental results from the literature and good agreements are generally found even for polycrystals with highly nonlinear or anisotropic grains.