Is it legal for an SEP airplane to fly above its service ceiling?
You didn't say which country you're asking about, but in the US it's legal. Your definition of service ceiling is correct, and there's no regulation that I know of that requires you remain below it.

The only clear case I can think of would be if the POH says that the service ceiling is an actual limitation and you shouldn't operate above it. Exceeding limitations in the POH is a violation of 14 CFR 91.9(a):


  Except as provided in paragraph (d) of this section, no person may
  operate a civil aircraft without complying with the operating
  limitations specified in the approved Airplane or Rotorcraft Flight
  Manual, markings, and placards


The AIM 5-3-3 requires you to report to ATC if you can't maintain a 500ft/min climb rate, so I suppose that not doing that could get you in trouble somehow. But there's no actual regulation, as far as I can see.

There are other, contrived scenarios that you could invent. If exceeding the service ceiling would require specific equipment or training that you don't have, then you could be in violation of various regulations, but that isn't because of the service ceiling itself.

And finally, there's the catch-all 91.13:


  No person may operate an aircraft in a careless or reckless manner so
  as to endanger the life or property of another.


If you do operate above the service ceiling and something goes wrong, then the FAA could bust you on that. Trying to get over mountains at or close to your service ceiling could be an example.