I was out of flying for nearly 13 years when I got back in. You may have to spend some time at a company you would rather not... but then again, with low hours etc... you probably cant be too choosey.
Bottom line, my background was all military and part 121 but did encounter some resistance. Get current, take an IPC etc. I happened to be in the right place at the right time... so much of this business is timing and connections.