I have a 32mb vps with ipxcore and a 64mb with lowendspirit, and both work great. The 32mb's don't really make economic sense for the host though, and they're no longer offered. The lowendspirit box holding the 64mb's got a ram upgrade, so all new vps's on that box have 128mb, and users with old 64mb's can get them upgraded on request (I haven't done this yet). Generally speaking the increasing cost of ipv4 addresses makes really tiny vps's unviable. lowendspirit (for those not familiar) are ipv6 vps's with some NATted ipv4 ports, so ipv4 considerations don't apply to them as much.
It would be interesting to offer a LES-like container as a vps product, e.g. a 1 or 2 GB KVM or Xen vps running 10 or 20 ipv6 openvz containers with LES-like NAT to a single ipv4 on the container vps.