I'm not sure if this question has been previously asked but here it is.

I've been searching and reading a lot of posts about the V4 4500 and the V5 5500 AGP cards. Since the V4 4500 is the only 4X AGP card, would it be faster than the V5 5500 even though it has only half the memory?

The only thing the Voodoo 4 4500 AGP has going for it is, 1.5V slot compatibility.  I would never advise you aquire this card, especially if you are just looking for high AGP rates, AGP rates are never the primary requisite for any graphics card.

The best mainstream retail VSA-100 board, for compatibility, is the 5500 PCI though these are hard to come by now and can be quite expensive on ebay.  If you have an older AGP 1.0 or AGP 2.0 Universal mobo, you can go for the 5500 AGP.  These can be fairly cheap and your best option.

I'm not sure if you know but the Voodoo4 doesn't only have half the memory, but it uses only a single VSA-100 GPU, whereas the Voodoo 5500 has two.