Halting problem = undecidability of all program properties?

[i]UNDERGRAD QUALITY[/i] incoming: An old thread on /math/ got me thinking about this. We know the typical proof uses
func G(x): if Halts(x, x) then loop forever
else false
and G(G) as a counterexample. Would this
func P(x): if ReturnsOdd(x, x) then 2
else 1
mean you can't prove a program always returns odd numbers because of P(P)? What about any other simple property like ``returns alphanumeric character'' or ``returns a valid s-expression''? You can always construct a function that ends in a contradiction by just returning the opposite thing.

>>33
No, just use the space of programs that don't call the Halts() function. Every single program in existence right now is in this space, including programs that don't halt and programs that do.