Okay, let me first emphasize that I sympathize with you. I'm not arguing with you. It's perfectly reasonable for you to expect there to be a natural expression that gets you to where you want. But what you've got to remember is that Mathematica is not a logic system. We can quibble about things around the edges, but in the main, all Mathematica is doing is evaluating expressions. So, when you are trying to assert something like x \[NotElement] Integers that is first an foremost just an expression, it's not an assertion. You're not registering an assertion into a logic framework.

If I understand you, you want Mathematica to "solve" Ceiling[x] - Floor[x] == 1 by telling you the domain in which it holds true. Logically, that domain should be x \[Element] Reals && x \[NotElement] Integers. Unfortunately, that expression simply doesn't resolve for all x. I don't have any knowledge about the inner workings of Mathematica's code, but I believe that the reason this is failing is because this expression isn't guaranteed to resolve for all of the relevant numeric values. For example,

With[
 {x = 2.0},
 x \[Element] Reals && x \[NotElement] Integers]
(* 2. \[NotElement] Integers *)

So, Mathematica was not able to determine the truth/falsity of that second term. Now, you may be thinking, "yes, but that value isn't in the domain of the solution", and I totally sympathize, but I still think that the underlying ambiguity of that expression is interfering. I could be totally wrong--we'd probably need someone more familiar with the underlying code to confirm.

I am sure that FullSimplify has a bunch of ad hoc rules that it knows how to apply, and maybe this particular case should be added to those rules, but for now it appears that it simply isn't. Maybe there's a very good reason for this, I don't know. But you're just beating your head against a wall here. Which leads me to ask what your real objective is. This looks more like some sort of test case for Mathematica itself than a computational problem that you need help with. What is it that you're actually trying to achieve? If this is just for curiosity's sake, then I think we've gone as far as we can. If this particular computation is interfering with some actual computational goal you're working toward, then maybe we can explore workarounds.

What do you mean? Here's another example:

In:  1 \[Element] Rationals
Out: True

In:  Ceiling[x] == 1 + Floor[x] /. x -> 12/5
Out: True

In:  FullSimplify[Ceiling[x] == 1 + Floor[x], x \[Element] Rationals]
Out: Ceiling[x] == 1 + Floor[x]

I think Hans Milton provided a good example, and your reply to that doesn't seem relevant. Here's another way to look at it:

FullSimplify[Ceiling[x] == Floor[x], x \[Element] Integers]
(* True *)

FullSimplify[Ceiling[x] == Floor[x], x \[Element] Reals]
(* Ceiling[x] == Floor[x] *)

So, you can interpret that as meaning, "when x is real, Mathematica cannot find a simplification that resolves the equality to true or false". And of course, like Hans showed, one example is 2.0. Indeed, we have

2 \[Element] Reals
(* True *)

So, we don't even need an expression with Real as its Head. Furthermore, consider this

2. \[Element] Integers
(* 2. \[Element] Integers *)

2. \[NotElement] Integers
(* 2. \[NotElement] Integers *)

meaning that Mathematica withholds commitment about the integer-valued-ness for a value that you expect to satisfy your assumptions. I think the answer to your original question depends upon the reason for that.