There are some resizing programs that have diferent algorithms than the tipical bicubic.
The main diference is that this kind of programs try to preserve the sharp edges between colours (the bicubic aproach is to soften the borders) so, in this case becouse the type of gaphic could work.
They don't perform miracles, but can help you to enlarge the image lets say 300%.
Here are 2 that I have used, but there are plenty more.
Photo Zoom http://www.benvista.com/photozoompro
Here is a post, written in spanish with some tests, auto translated in google https://translate.googleusercontent.com/translate_c?act=url&depth=1&hl=es&ie=UTF8&prev=_t&rurl=translate.google.com&sl=es&tl=en&u=http://forobeta.com/diseno-grafico/359857-programas-ampliar-imagenes-algoritmos.html&usg=ALkJrhjGqb1yXEf17Hdkm7B2URpUycJL8w
1) Before trying to enlarge them I would clean a bit the image, enhance a bit the colours and clean any jpg artifacts.
2) Test diferent algorithms untill I find something decent. Don't force the resizing too much. I would recomend 300% max.
3) Sharpen a bit the final result.
4) Think the posibility to vectorize this result.
5) Clean and optimize this vectorized version. This could work as a "new version" and the client should consider having this vectorized version as the "official" logo.
But at the end there is no way of resizing a bitmap in a magical way.