Two separate things going on here:
1) Looks like there's a bug with "month" and "year" relative operations -- we're not zeroing out the range correctly (#$*! Java Calendar APIs, some fields are 0-indexed and some are 1-indexed and so easy to get them mixed up). I've filed bug 26744 on this.
2) Your comment "I would have thought date:-0month would give mails from 4th Mar to today, 4th Apr" is not correct because you aren't taking into account the matching window. It's important to understand that the "date" operator has an implicit matching window. When you specify date: you don't really mean an exact time, you really mean some kind of a range. Sometimes you want to refer to a calendar day (midnight-midnight), sometimes an hour (3:00 to 4:00), sometimes a week (sunday-sunday), etc. In order to take this into account, when you specify a relative date the granularity of the range is implied by the operator you use.
The reason for this will become clear if you look at the most common cases. Lets assume that the current date is 4/4/2008 and the time is 2:36pm.
Remember the goal here is not to create something infinitely expressible (you can always just enter "date:>=3/4/2008 and date:<=3/5/2008" and take complete control over the range yourself) but instead to allow people to quickly specify searches they have might have to do.
date:-1h "last hour" -- 1pm - 2pm on 4/4
date:-1d "yesteday" -- midnight on 4/3 until midnight on 4/4
date:-1w "last week" -- Sunday 3/23 to Sunday 3/30
date:-1m "last month" -- 3/1 to 4/1
date:-1y "last year" -- 2007
So date:-0m should mean "4/1 to 5/1"....but it's broken (bug 26744 ). If you really really want the exact day that happened a month ago, you want "-31d" (or -30d or -28d, depending on the month) -- there's no way to express it directly in a relative date...although honestly I don't think it's that useful (do you have a real-world use case for this?)
Now -- just because I'm on a roll -- let's see what happens when you use a relative date with the "before" or "after" operators:
The last two are counterintuitive, but correct. "-31d" evaluates to the range (3/4/2008 0:00 to 3/5/2008 0:00) and after means ">= the end of the range.". This is easiest to grok if you think that "-1d" means "yesterday" so after:-1d means "after yesterday". For after:-1m you're talking about "After last month" which is "this month".
after:-1d means "after yesterday" -- so today or later
after:-2h means "after the hour that was 2 hours ago" -- so after 1:00 (0 hours ago is 2-3, 1 hour ago is 1-2, so 2 hours ago is 12-1)
after:-1y means "date:>=1/1/2008"
after:-31d means "date:>=3/5/2008"
after:-1m means "date:>=4/1/2008"