The syntax you tried is actually ambigous. Depending on how many days are in the month, some months it will run on odd days and some on even. This is because the way it is calculated takes the total number of posibilities and divides them up. You can over-ride this strage-ish behavior by manually specifying the day range and using either an odd or even number of days. Since even day scripts would never run on the 31st day of longer months, you don't loose anything using 30 days as the base for even-days, and by specifying specifically to divide it up as if there were 31 days you can force odd-day execution.
The syntax would look like this:
# Will only run on odd days:
0 0 1-31/2 * * command
# Will only run on even days:
0 0 2-30/2 * * command
Your concern about months not having the same number of days is not important here because no months have MORE days than this and for poor February, the date range just won't ever match the last day or two, but it will do no harm having it listed.
The only 'gotcha' for this approach is that if you are on an odd day cycle, following months with 31 days your command will also run on the first of the month. Likewise if you are forcing an even cycle, each leap year will cause one three day cycle and the end of February. You cannot really get around the fact that any regular pattern of "every other day" is not always going to fall on even or odd days in every month and any way you force this you will either have an extra run or be missing a run between months with miss-matched day counts.