Verizon DSL service

If you live under Verizon Domination than I think you can get cable in you area. DROP VERIZON, I used them before they are no good, I had more problems with them then with having to use a dial up connection. Instead get cable; its faster the same price and its always on.
As for your problem, I was able to get VPN working over Verizons DSL, The solution I used was WINNT PPTP protocol and RAS. The client mahine can be any Windows machine that has Dial Up Networking 3.1 and above (win98 ships with VPN, for win95 you will have to download it from Microsofts web site).
However I did run into problems when trying to configure it on a computer that had more than one NIC installed on that comptuer and was running win9x for the Oprating System.
The best way to get it work (that is if you have more than one NIC b/c you are also connecting to a LAN) is to get a WAN hub, it has one port for the DSL/Cable connection and you connect all computers to the other ports you can even uplink other hubsto it. It can act as a DHCP server, Router and/or gateway and its only about $150.
Once this is up and running just configure the WAN hub that it should forward VPN requests to the VPN server machine (you will have to find out exectly what port yousolution of VPN runs on, I think PPTP runs on port # 1723 or 1732, I dont remember).