This is going to sound crazy, but an external modem (remember those?) in auto-answer mode will probably accomplish this. The only issue is the "hard reboot" option. A small timer circuit and relay would potentially let you use the "BREAK" signal to accomplish this (dial up, notice "it's dead, Jim", then send BREAK to cycle the relay or the PC's reset line). I'm sure someone makes a little box to do something like this, but it also shouldn't be terribly difficult to build.
Any reason you need the VPN option? Ma Bell's system rarely breaks, and when it does, the data services usually go with it, even if Ma Bell isn't your ISP. Another PC with a serial cable hooked between the two PCs could accomplish this in a simple, albeit bulky manner. You'd think it would be expensive, but a trash PC is cheaper than these little OOB management devices often are. Said "companion" PC could also participate in the hard reboot procedure using e.g. the parallel port to toggle the reset line of the firewall. If you have this PC, you could also just dump the modem in it for dial-up access.
If the appliance is "hackable" (runs a modifiable OS install), you might also look into a watchdog solution. If it locks up, this will power cycle it. Such a solution could also consist of an external PC to monitor status (e.g. ping something) and reboot the firewall if that fails. I've even seen people rig up CD trays to hit power buttons for this purpose!