patented game

for the most part, you will potentially run into problems if you submit the game and say you've already got it patented (it makes you look litigious, which will make them not want to touch it with a ten foot pole). but it's a sticky thing, because you want to be up front about those sorts of things. this, as all things, will depend on the company you submit it to. (and i'll try to avoid bagging on patenting in general, since once the money has been spent, the point is already moot)

aside from that, though, it's the normal advice for submitting to companies:
is it still an abstract? then contact an abstract company, like gigamic or nestor games.
is it no longer an abstract? look for companies who produces games with a similar play feel (but that don't have games that would be directly competing with yours, theme/play wise). then narrow the field to those that use packaging and/or components similar to what you'd anticipate your game needing. contact the most likely first, and then move down your list.