I have a device that is plugged into an AC outlet.  At regular
intervals, power is intentionally cut (through some automated system
that I have no access to) in order to disable this device.

I am replacing the device with a new one that I can turn off and on
through software controls (better than yanking the plug).  However,
the only way to know when I should soft power it off / on is when the
original AC outlet is turned on and off.

I am looking for something I can plug into that original outlet to
detect when the power is enabled or not.  I will need to poll this
unit to determine whether or not I should turn on the other device or
not.

The easiest solution I have come up with thus far is to purchase a
small, embedded webserver or the like  (IE:
http://www.siteplayer.com), assign it an IP, and periodically ping
that IP to determine if it is still getting power.  If the power goes
off, I will get no ping response, and I will know to soft-power off
the other device.  When ping resumes, I will know that power has been
restored, and I should enable the other device.

I realize this is a bit clunky and quite a hack, but it seems to be
the most straight-forward approach I can come up with at the moment. 
I am intrigued by the IP approach, since I would be able to simply run
cat5 to the unit, making setup in multiple locations easier.

Price and reliability are more important to me than elegance, though
an elegant detection solution would be optimal.

Please ask if you have any questions about the setup.

It's not clear from your question whether you want to sit still for
these power interruptions, or, as an alternative, you would prefer not
to have to shut down the device at all.

In either case, a UPS might be a solution for you.  If you want to
stop the device from going down, plug it into the uninteruptible power
source.  If you just want to find out when power has been disabled,
but still allow the device to crash whenever the power is interrupted,
then plug it into the wall, and plug the UPS into the wall, too.  The
UPS will generate an SNMP trap, which you can monitor using any
monitoring program that you want to use.

You might want to clarify your question make this clearer.

Here's a UPS that will work for you:
http://www.powerware.com/UPS/Connectivity/ConnectUPS.asp

Sorry if I was not clear.  

I'll try to clarify with a realistic scenario.  

Currently, there is a 35mm projector controlling the power plug. 
Attached to that plug is a simple slide projector.  When a movie
starts, the projector kills the power to that plug, essentially
stopping the slide projection.  The slide projector is used for
before-movie advertising.

This slide projector will be replaced with a small digital projector. 
This digital projector will be plugged into constant-power AC.  I will
need to detect when the original plug loses power, in order to close
the shutter on the digital projector.

The device I require will need to do this detection.   As I mentioned,
price is of concern.  I am able to get something working with an
embedded IP server for under $50.  For this reason, using a UPS device
would not be suitable, and would again be overkill.