I think I mentioned a long ways back that your provider was running OpenVZ, which is known to have problems with Java and any other memory-hungry app. Depending on how it’s configured, OpenVZ can be made to more or less lie about how much memory is available, giving it to you initially then taking it away if any other virtualized domain demands it.
I might have had a more little confidence than the others in the more expensive tier, assuming it might be Xen instead, which cannot pull these shenanigans. Of course I would have actually checked out the specs before cracking open my wallet…