Silvery - 8:56 pm on May 16, 2010 (gmt 0)

Some are calling these "enhanced listings" or "sponsored icons", and Google appears to call these "tags":

[maps.google.com...]

You have to use the special signup form to apply to have these. Also, Google appears to be only offering this product on a trial basis in some cities at the moment.