Probably several months, at least...think it happened in May 2011. It's most likely not feasible today, as you won't see much more than 10-15 MH/s from it, depending on what your VPS uses (mine have given me 4-8 Xeon or Opteron cores). The only point in its favor now is that if you already have a VPS for other purposes, mining on it won't cost you anything extra.