Is perpetual motion impossible? I know that a perpetual motion machine (a device that produces work without an energy source) would violate several physical laws, the first that comes to mind being the conservation of energy. I also understand that a claim that perpetual motion is possible would probably not be congruent with the scientific method, occum's razor, etc.
What I am interested in is whether there exists some logical and intuitively meaningful (to they lay person) demonstration that perpetual motion is universally impossible, based only on axioms rooted in observable physical phenomena, rather than the obvious reasons why it is merely improbable and incompatible with some of our physical laws.
Certain violations of physical laws, such as travelling faster than the speed of light, can be shown to be unlikely as they would cause paradoxes or logical impossibilities, such as a violation of causality. In that instance, the axioms needed to establish a paradox (time dilation) are empirically observable, and a counter-claim would require the existence of new paradox-resolving laws that are not established, or the permission of paradoxes which is difficult to imagine.
Conversely, the idea that some invention is impossible on the basis of its violation of a physical law alone is difficult because it requires a proof of impossibility.
So, without relying on the assertion that a physical law is omnipresent (e.g. conservation of energy), is there some impossibility or logical paradox that would arise from the existence of a machine that could produce work without indefinitely without an energy source?
Finally, I'm very aware that perpetual motion is a bit of a dirty word and will likely touch a nerve with people, so please take the time to let me know how I can make this question less offensive and avoid the inevitable down-votes.
 A: Instead of thinking about conservation of energy, you should look instead at the second law of thermodynamics (which perpetual motion machines almost always violate). The concept of entropy is entirely numerical (log of the number of microstates of a system), so violating the laws of thermodynamics/statistical mechanics is tantamount to violating the laws of statistics, which are purely logically derived! And if you find yourself having to break a field of mathematics to show your machine works, I'd count that as a paradox in my book.
A: 
So, without relying on the assertion that a physical law is omnipresent (e.g. conservation of energy), is there some impossibility or logical paradox that would arise from the existence of a machine that could produce work without indefinitely without an energy source?

This seems to be your core question.
The problem here is that if the machine existed, it would de facto adhere to the physical laws of it's universe, as it is part of that universe, so the machine's laws are part of that universe's laws.
All I can say is that we have no reason to presume that a paradox in laws we think of as governing the universe imply there's anything wrong with the Universe.
It does not even tell us that our deduced laws are wrong, as we don't have any basis for asserting a universe has to be governed by paradox-free laws.  If we built it we built it from our laws, so our laws must produce the paradox ( if there is one ).  Either we're right ( and we've no basis to assume we're wrong as the darn machine works ) and our laws are fine, or we're wrong and why did the darn machine work in the first place ?
And while it's fashionable to believe that the Universe must follow mathematical laws, we've no basis for that either.  So far we're one step ahead of the law ( sorry ) in constructing deviously clever mathematical models of the universe ( well one step close behind really ), but we've no basis for assuming that such models are the underlying thing.  We're all gonna feel awful stupid if there is a God and he /she just magics stuff into existence and sod the rules and never mind the arithmetic.  But we don't know it ain't that way.
So if it existed, your machine would just be a pain in the backside to explain at parties and we'd all have to get religion anyway.  But it would exist and so would any paradox that came with it, and that would be the way the universe worked and there'd be no problem with that.
Until the universe disappeared up it's own backside, of course. :-)
But I can fix this.
The trick here is to out-think the Universe.  I'll be a monkey's uncle ( thanks, Darwin ) if I let the universe take itself away from me.  If we design the machine but don't actually do anything daft like build it, we don't end up with any actual paradoxes hanging around making us look foolish and making a mockery of all that time I spent learning complex analysis ( or trying to ).
Now where's my Nobel prize ?  And a decent drink, while you're at it. :-)
A: The general axiom that you can appeal to is "there is no isolated case where heat spontaneously flows from a cold object into a hotter object. To do that you need some external energy source pulling the heat specially out of the colder object and putting it into the hotter object."
In other words, refrigerators are possible but they always require a power source.
A perpetual motion machine, generating energy from nothing, violates this by definition because you can connect it to the power cord of a refrigerator and then (perpetual motion device) + (refrigerator) is a device for spontaneously moving heat from cold to hot. 
A: The difference between an axiom and a theorem is taste. Once you define your axioms the theorems that follow are as valid as the axioms. In fact you can change the theory and use the theorems as axioms and the axioms as theorems.
A perpetuum mobile of the first kind, which violates conservation of energy, is thus incompatible with the laws of physics. A perpetuum mobile of the second kind, which can reduce the entropy of the universe, is less strict. It can be shown to be  highly (extremely) unlikely in our universe. But it is not that unlikely if the laws of physics were different. See for example http://www.wolframscience.com/, in which computer simulations show that some cellular automata non trivial laws do not necessarily evolve into increasing entropy but it makes it fluctuate with large likelihood. However if this fact can be used to make a perpetuum mobile in such universe, I do not think it been studied.
A: It's simply down to lack of observation: as the scientist community, we have never seen a reproducible perpetual motion machine, or a violation of the laws - particularly either conservation of energy or the second law of thermodynamics - that such a machine would needfully imply.
You seem to place a great deal of weight on violation of causality as a reason for accepting that faster than light travel is not possible - that this is somehow a purely logical proof supraluminal impossibility. This, however, is not so - here we have exactly the same kind of grounds for disbelief in supraluminal signalling as we do for disbelief in perpetual motion. We've never seen a cause come before an effect, or, more precisely, certain physical processes experimentally seem to have a consistent time order, we've never seen them play out in any other order, so we postulate that this order must be observer independent. See my comments on the physics interpretation of the notion of causality in my answer here and here - it's a wholly experimental notion and has nothing to do with axiomatic mathematical proof. Indeed an abstract definition of causality divorced from appeal to experiment may itself be impossible.
The denial of supraluminal signalling on the grounds that it would violate causality thus only seems to be on a different level from the denial of perpetual motion. There is no in-principle difference insofar that we deny them simply because they would tell against all experiments we've done so far in each case. Causality is, perhaps, more accessible to us because we've seen physical processes conform to consistent time ordering all our lives. A child of four would be immediately bewildered if the shards of a shattered glass jumped off the floor and reassembled themselves. Added to this is perhaps our cultural / religious prejudice against and thus resistance to thought about "time" in terms other than "common sense" ones that makes causality seem such a big deal compared with other purely experimental notions. 
A: Suppose you have a point mass going along a path in a uniform gravitational field and its acceleration is always gravitational acceleration plus an acceleration vector perpendicular to the part of the path it's on. If we define potential energy to be mgh and its kinetic energy to be mv^2/2, then it can be mathematically proven that its potential energy plus its kinetic energy will remain constant. On the other hand, I believe the second law of thermodynamics has never been proven from a simplified quantum mechanical theory where the gravitational constant is zero and electrons and nuclei are point masses with no nuclear chemistry, so a perpetual motion machine of the second kind might be a real possibility as observed on time scales too short for other effects to occur like the sun burning out of energy freezing the entire Earth or radioactive decay. My answer at Is there any proof for the 2nd law of thermodynamics? explains why the second law of thermodynamics might not be true according to that simplified theory.
