RAM is not the critical part of a transcode, CPU is. Since it is working stream to stream, fairly minimal memory actually has to be required if the encoder is operating efficiently. The memory speed does matter for scratch space for the processor, but not so much the quantity.
The CPU (or GPU if using GPU optimized encoding) is what does all the work and most likely your VPS has insufficient processing power. Video encoding is extremely intensive. It is one of the primary reasons that video editing workstations tend to be large powerful computers, often with multiple graphics cards to spread the load to GPU processing or dedicated hardware encoding peripherals.
Depending on the length of video represented by that 500mb file, this isn't at all surprising. Even on my 2.9ghz quad core i7, it still takes roughly 2 to 3 times the length of the original video to complete a high quality 2 pass VBR encoding (and all 8 virtual cores are at 99% non-stop the entire time). You may not be doing two pass, but you also likely don't have nearly as much processing power being thrown at it.